Merge branch 'develop' into claude/string-view-convertible-keys-5663

Conflicts:
- docs/mkdocs/docs/api/basic_json/count.md: kept the PR's string_view note on overload 2 and develop's new item 3 (deleted integral-key overload)
- docs/mkdocs/docs/api/basic_json/find.md: same as count.md
- docs/mkdocs/docs/api/basic_json/value.md: kept develop's integral-key note on item 1 and the PR's string_view note on item 2

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

docs/mkdocs/docs/api/basic_json/at.md

@@ -224,5 +224,7 @@ Strong exception safety: if an exception occurs, the original value stays intact
 
 1. Added in version 1.0.0.
 2. Added in version 1.0.0.
-3. Added in version 3.11.0.
+3. Added in version 3.11.0. Fixed in version 3.13.0 to consistently accept `std::string_view`-convertible keys, as
+   already supported by [`operator[]`](operator[].md), [`value`](value.md), [`find`](find.md), and other lookup
+   functions.
 4. Added in version 2.0.0.

docs/mkdocs/docs/api/basic_json/contains.md

@@ -119,7 +119,9 @@ Logarithmic in the size of the JSON object.
 ## Version history
 
 1. Added in version 3.11.0.
-2. Added in version 3.6.0. Extended template `KeyType` to support comparable types in version 3.11.0.
+2. Added in version 3.6.0. Extended template `KeyType` to support comparable types in version 3.11.0. Fixed in
+   version 3.13.0 to consistently accept `std::string_view`-convertible keys, as already supported by
+   [`operator[]`](operator[].md), [`at`](at.md), [`value`](value.md), and other lookup functions.
 3. Added in version 3.7.0.
 4. Deleted overloads for integral key types added in version 3.13.0 to reject such calls at compile time instead of
    causing undefined behavior at runtime.

docs/mkdocs/docs/api/basic_json/count.md

@@ -84,6 +84,8 @@ Logarithmic in the size of the JSON object.
 ## Version history
 
 1. Added in version 3.11.0.
-2. Added in version 1.0.0. Changed parameter `key` type to `KeyType&&` in version 3.11.0.
+2. Added in version 1.0.0. Changed parameter `key` type to `KeyType&&` in version 3.11.0. Fixed in version 3.13.0 to
+   consistently accept `std::string_view`-convertible keys, as already supported by [`operator[]`](operator[].md),
+   [`at`](at.md), [`value`](value.md), and other lookup functions.
 3. Deleted overload for integral key types added in version 3.13.0 to reject such calls at compile time instead of
    causing undefined behavior at runtime.

docs/mkdocs/docs/api/basic_json/erase.md

@@ -213,5 +213,7 @@ Strong exception safety: if an exception occurs, the original value stays intact
 1. Added in version 1.0.0. Added support for binary types in version 3.8.0.
 2. Added in version 1.0.0. Added support for binary types in version 3.8.0.
 3. Added in version 1.0.0.
-4. Added in version 3.11.0.
+4. Added in version 3.11.0. Fixed in version 3.13.0 to consistently accept `std::string_view`-convertible keys, as
+   already supported by [`operator[]`](operator[].md), [`at`](at.md), [`value`](value.md), and other lookup
+   functions.
 5. Added in version 1.0.0.

docs/mkdocs/docs/api/basic_json/find.md

@@ -88,6 +88,8 @@ Logarithmic in the size of the JSON object.
 ## Version history
 
 1. Added in version 3.11.0.
-2. Added in version 1.0.0. Changed to support comparable types in version 3.11.0.
+2. Added in version 1.0.0. Changed to support comparable types in version 3.11.0. Fixed in version 3.13.0 to
+   consistently accept `std::string_view`-convertible keys, as already supported by [`operator[]`](operator[].md),
+   [`at`](at.md), [`value`](value.md), and other lookup functions.
 3. Deleted overloads for integral key types added in version 3.13.0 to reject such calls at compile time instead of
    causing undefined behavior at runtime.

docs/mkdocs/docs/api/basic_json/value.md

@@ -195,7 +195,9 @@ changes to any JSON value.
 1. Added in version 1.0.0. Changed parameter `default_value` type from `const ValueType&` to `ValueType&&` in version
    3.11.0. Deleted overload for integral key types added in version 3.13.0 to reject such calls at compile time
    instead of causing undefined behavior at runtime.
-2. Added in version 3.11.0. Made `ValueType` the first template parameter in version 3.11.2.
+2. Added in version 3.11.0. Made `ValueType` the first template parameter in version 3.11.2. Fixed in version 3.13.0
+   to consistently accept `std::string_view`-convertible keys, as already supported by
+   [`operator[]`](operator[].md), [`at`](at.md), [`find`](find.md), and other lookup functions.
 3. Added in version 2.0.2. Extended to work with arrays in version 3.13.0, including fixing an issue where resolving
    `ptr` through an array unexpectedly threw `out_of_range` instead of returning the resolved element (or
    `default_value`, as documented).

include/nlohmann/detail/meta/type_traits.hpp

@@ -748,6 +748,30 @@ using is_usable_as_key_type = typename std::conditional <
                               std::true_type,
                               std::false_type >::type;
 
+#ifdef JSON_HAS_CPP_17
+// type trait to check if KeyType can only be used as an object key after
+// converting it to std::string_view: it is convertible to std::string_view, the
+// object's comparator cannot compare it with object_t::key_type directly, but
+// can compare a std::string_view. JSON pointers and JSON iterators are ruled out
+// first, so that the conversion checks are never instantiated for them (a JSON
+// pointer's deprecated conversion to string_t would be named otherwise).
+template < typename BasicJsonType, typename KeyTypeCVRef, typename KeyType = uncvref_t<KeyTypeCVRef>,
+           bool = is_json_pointer<KeyType>::value || is_json_iterator_of<BasicJsonType, KeyType>::value >
+struct is_string_view_convertible_key_type : std::false_type {};
+
+template<typename BasicJsonType, typename KeyTypeCVRef, typename KeyType>
+struct is_string_view_convertible_key_type<BasicJsonType, KeyTypeCVRef, KeyType, false>
+    : std::integral_constant < bool,
+      std::is_convertible<KeyTypeCVRef, std::string_view>::value
+      && !is_usable_as_key_type<typename BasicJsonType::object_comparator_t,
+      typename BasicJsonType::object_t::key_type, KeyTypeCVRef, true, false>::value
+      && is_usable_as_key_type<typename BasicJsonType::object_comparator_t,
+      typename BasicJsonType::object_t::key_type, std::string_view, true, false>::value > {};
+#else
+template<typename BasicJsonType, typename KeyTypeCVRef>
+struct is_string_view_convertible_key_type : std::false_type {};
+#endif
+
 // type trait to check if KeyType can be used as an object key
 // true if:
 //   - KeyType is comparable with BasicJsonType::object_t::key_type
@@ -761,9 +785,7 @@ using is_usable_as_basic_json_key_type = typename std::conditional <
      typename BasicJsonType::object_t::key_type, KeyTypeCVRef,
      RequireTransparentComparator, ExcludeObjectKeyType>::value
      && !is_json_iterator_of<BasicJsonType, KeyType>::value)
-#ifdef JSON_HAS_CPP_17
-    || std::is_convertible<KeyType, std::string_view>::value
-#endif
+    || is_string_view_convertible_key_type<BasicJsonType, KeyTypeCVRef>::value
     , std::true_type,
     std::false_type >::type;
 

include/nlohmann/json.hpp

@@ -807,6 +807,24 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         return it;
     }
 
+    /// @brief the key to look up an object member with: the key itself, or its
+    ///        std::string_view if the object can only be searched with that
+    template < typename KeyType, detail::enable_if_t <
+                   !detail::is_string_view_convertible_key_type<basic_json_t, KeyType>::value, int > = 0 >
+    static KeyType && lookup_key(KeyType && key) noexcept
+    {
+        return std::forward<KeyType>(key);
+    }
+
+#ifdef JSON_HAS_CPP_17
+    template < typename KeyType, detail::enable_if_t <
+                   detail::is_string_view_convertible_key_type<basic_json_t, KeyType>::value, int > = 0 >
+    static std::string_view lookup_key(KeyType && key)
+    {
+        return std::forward<KeyType>(key);
+    }
+#endif
+
     /// @brief erase an element from the object and return the following one
     /// Not every map returns an iterator from erase(iterator): some containers
     /// (e.g., Abseil's hash maps) return void to avoid computing a successor
@@ -2767,7 +2785,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             JSON_THROW(type_error::create(304, detail::concat("cannot use at() with ", type_name()), this));
         }
 
-        auto it = m_data.m_value.object->find(std::forward<KeyType>(key));
+        auto it = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         if (it == m_data.m_value.object->end())
         {
             JSON_THROW(out_of_range::create(403, detail::concat("key '", string_t(std::forward<KeyType>(key)), "' not found"), this));
@@ -2805,7 +2823,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             JSON_THROW(type_error::create(304, detail::concat("cannot use at() with ", type_name()), this));
         }
 
-        auto it = m_data.m_value.object->find(std::forward<KeyType>(key));
+        auto it = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         if (it == m_data.m_value.object->end())
         {
             JSON_THROW(out_of_range::create(403, detail::concat("key '", string_t(std::forward<KeyType>(key)), "' not found"), this));
@@ -2948,7 +2966,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // operator[] only works for objects
         if (JSON_HEDLEY_LIKELY(is_object()))
         {
-            auto result = m_data.m_value.object->emplace(std::forward<KeyType>(key), nullptr);
+            auto result = m_data.m_value.object->emplace(lookup_key(std::forward<KeyType>(key)), nullptr);
             return set_parent(result.first->second);
         }
 
@@ -2964,7 +2982,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // const operator[] only works for objects
         if (JSON_HEDLEY_LIKELY(is_object()))
         {
-            auto it = m_data.m_value.object->find(std::forward<KeyType>(key));
+            auto it = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
             JSON_ASSERT(it != m_data.m_value.object->end());
             return it->second;
         }
@@ -2974,8 +2992,10 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
   private:
     template<typename KeyType>
-    using is_comparable_with_object_key = detail::is_comparable <
-        object_comparator_t, const typename object_t::key_type&, KeyType >;
+    using is_comparable_with_object_key = std::integral_constant < bool,
+        detail::is_comparable <
+            object_comparator_t, const typename object_t::key_type&, KeyType >::value
+        || detail::is_string_view_convertible_key_type<basic_json_t, KeyType>::value >;
 
     template<typename ValueType>
     using value_return_type = std::conditional <
@@ -3362,7 +3382,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             JSON_THROW(type_error::create(307, detail::concat("cannot use erase() with ", type_name()), this));
         }
 
-        const auto it = m_data.m_value.object->find(std::forward<KeyType>(key));
+        const auto it = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         if (it != m_data.m_value.object->end())
         {
             m_data.m_value.object->erase(it);
@@ -3389,7 +3409,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                  detail::is_usable_as_basic_json_key_type<basic_json_t, KeyType>::value, int> = 0>
     size_type erase(KeyType && key)
     {
-        return erase_internal(std::forward<KeyType>(key));
+        return erase_internal(lookup_key(std::forward<KeyType>(key)));
     }
 
     /// @brief remove element from a JSON array given an index
@@ -3469,7 +3489,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
         if (is_object())
         {
-            result.m_it.object_iterator = m_data.m_value.object->find(std::forward<KeyType>(key));
+            result.m_it.object_iterator = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         }
 
         return result;
@@ -3485,7 +3505,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
         if (is_object())
         {
-            result.m_it.object_iterator = m_data.m_value.object->find(std::forward<KeyType>(key));
+            result.m_it.object_iterator = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         }
 
         return result;
@@ -3508,7 +3528,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     size_type count(KeyType && key) const
     {
         // return 0 for all nonobject types
-        return is_object() ? m_data.m_value.object->count(std::forward<KeyType>(key)) : 0;
+        return is_object() ? m_data.m_value.object->count(lookup_key(std::forward<KeyType>(key))) : 0;
     }
 
     /// @brief check the existence of an element in a JSON object
@@ -3526,7 +3546,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     JSON_HEDLEY_WARN_UNUSED_RESULT
     bool contains(KeyType && key) const
     {
-        return is_object() && m_data.m_value.object->find(std::forward<KeyType>(key)) != m_data.m_value.object->end();
+        return is_object() && m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key))) != m_data.m_value.object->end();
     }
 
     /// @brief check the existence of an element in a JSON object given a JSON pointer
@@ -6106,256 +6126,21 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     {
         // the patch
         basic_json result(value_t::array);
-        diff_recursively(result, source, target, path, 0);
-        return result;
-    }
 
-  private:
-    /// @brief two arrays or two objects @ref diff_iteratively is diffing
-    struct diff_frame
-    {
-        diff_frame(const basic_json* source_, const basic_json* target_, const std::size_t path_length_) noexcept
-            : source(source_), target(target_), path_length(path_length_)
-        {}
-
-        // declared for GCC's -Weffc++, which asks for them in a class with
-        // pointer members and a non-trivial destructor; the exception
-        // specifications are left implicit, as GCC 4.8 rejects explicit ones
-        // that differ from them
-        diff_frame(const diff_frame&) = default;
-        diff_frame(diff_frame&&) = default;
-        diff_frame& operator=(const diff_frame&) = default;
-        diff_frame& operator=(diff_frame&&) = default;
-        ~diff_frame() = default;
-
-        /// the values being diffed, both arrays or both objects
-        const basic_json* source;
-        const basic_json* target;
-        /// the length of their path in `current_path`
-        std::size_t path_length;
-        /// arrays: the next index to diff
-        std::size_t index = 0;
-        /// objects: the next member of source to look at
-        const_iterator member{}; // NOLINT(readability-redundant-member-init)
-        /// objects: the keys common to both, in source's order
-        std::vector<typename object_t::key_type> common_keys{}; // NOLINT(readability-redundant-member-init)
-        /// objects: the next entry of common_keys
-        std::size_t next_common = 0;
-        /// objects: the "add" operations for keys only target has
-        basic_json added_ops{}; // NOLINT(readability-redundant-member-init)
-    };
-
-    // The operations of a diff are built by the functions below rather than
-    // where they are needed: building one takes several temporaries, and
-    // unoptimized builds give each temporary a stack slot of its own in the
-    // function it appears in. In diff_recursively, which is on the call stack
-    // once per nesting level, that made every level cost kilobytes of stack.
-
-    /// @brief append a "replace" operation for @a path with @a value to @a result
-    static void diff_replace(basic_json& result, const string_t& path, const basic_json& value)
-    {
-        result.push_back(
-        {
-            {"op", "replace"}, {"path", path}, {"value", value}
-        });
-    }
-
-    /// @brief append a "remove" operation for @a path to @a result
-    static void diff_remove(basic_json& result, const string_t& path)
-    {
-        result.push_back(object(
-        {
-            {"op", "remove"}, {"path", path}
-        }));
-    }
-
-    /// @brief append an "add" operation for @a path with @a value to @a result
-    static void diff_add(basic_json& result, const string_t& path, const basic_json& value)
-    {
-        result.push_back(
-        {
-            {"op", "add"}, {"path", path}, {"value", value}
-        });
-    }
-
-    /// @brief append the "remove" operations for the elements of array
-    ///        @a source from @a index on, and the "add" operations for the
-    ///        elements of array @a target from source's size on, to @a result
-    static void diff_array_tails(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path, const std::size_t index)
-    {
-        // remove my remaining elements, highest index first; appending
-        // in that order avoids the quadratic reinsertion done before
-        for (std::size_t j = source.size(); j > index; --j)
-        {
-            diff_remove(result, detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1)));
-        }
-
-        // add other remaining elements
-        for (std::size_t i = source.size(); i < target.size(); ++i)
-        {
-            diff_add(result, detail::concat<string_t>(path, "/-"), target[i]);
-        }
-    }
-
-    /*!
-    @brief compare the keys of objects @a source and @a target
-
-    If object_t does not keep its members in insertion order, or if the keys
-    both objects have are in the same order in both, and the keys only
-    @a target has come after them, stores the keys common to both in
-    source's order in @a common_keys, stores the "add" operations for the keys
-    only @a target has in @a added_ops, and returns true: the caller then diffs
-    the objects member by member. Otherwise, appends operations that remove
-    every member of @a source and add every member of @a target to @a result,
-    and returns false.
-    */
-    static bool diff_object_keys(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path, std::vector<typename object_t::key_type>& common_keys,
-                                 basic_json& added_ops)
-    {
-        // first pass: record, for every source key, whether it is
-        // common to both objects (in source's iteration order) or
-        // was deleted (i.e., in source but not in target) -- this is
-        // a by-product of the target.find() call already needed to
-        // tell the two cases apart, so it adds no extra lookups. The
-        // "remove" ops themselves are emitted later, interleaved
-        // with the per-key diffs in the caller's fast path, to match
-        // source's original iteration order (as the original,
-        // pre-reordering-aware implementation did) instead of
-        // grouping all removes before all per-key diffs.
-        std::vector<typename object_t::key_type> common_keys_source_order;
-        for (auto it = source.cbegin(); it != source.cend(); ++it)
-        {
-            if (target.find(it.key()) != target.end())
-            {
-                common_keys_source_order.push_back(it.key());
-            }
-        }
-
-        // second pass: find keys that were added (i.e., in target but
-        // not in source), and record the keys common to both, in
-        // target's iteration order -- again a by-product of the
-        // source.find() call already needed to detect added keys. At
-        // the same time, determine whether every added key comes
-        // after every common key in target's order (a precondition
-        // for the fast path, which only ever appends new keys
-        // at the very end). Both are only needed for an object_t that
-        // keeps its members in insertion order, such as the one
-        // backing `ordered_json`; for any other object_t, the fast
-        // path is always taken and they are not computed.
-        // The patch ops for keys that were added (i.e., in target but not
-        // in source) are built here so the fast path can reuse
-        // them without a second source.find() per target key. Only
-        // used by the fast path -- the slow (reordering) path
-        // rebuilds "add" ops for every key itself.
-        std::vector<typename object_t::key_type> common_keys_target_order;
-        bool new_keys_form_suffix = true;
-        bool seen_new_key = false;
-        for (auto it = target.cbegin(); it != target.cend(); ++it)
-        {
-            if (source.find(it.key()) == source.end())
-            {
-                seen_new_key = true;
-                diff_add(added_ops, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
-            }
-            else
-            {
-#ifdef JSON_HEDLEY_MSVC_VERSION
-#pragma warning(push )
-#pragma warning(disable : 4127) // ignore warning to replace if with if constexpr
-#endif
-                if (detail::is_ordered_map<object_t>::value)
-                {
-                    common_keys_target_order.push_back(it.key());
-                    if (seen_new_key)
-                    {
-                        new_keys_form_suffix = false;
-                    }
-                }
-#ifdef JSON_HEDLEY_MSVC_VERSION
-#pragma warning( pop )
-#endif
-            }
-        }
-
-        // Only an object type that keeps its members in insertion
-        // order, such as nlohmann::ordered_map, can need reordering:
-        // patch() appends a new member at the end of such an object.
-        // Any other object type places its members itself - std::map
-        // in key order, a hash map in an order its operator== ignores -
-        // so a member-by-member diff always reproduces target there.
-        if (!detail::is_ordered_map<object_t>::value
-                || (common_keys_source_order == common_keys_target_order && new_keys_form_suffix))
-        {
-            // fast path: order of common keys already matches (or the
-            // object_t's iteration order does not depend on
-            // insertion history), so a plain per-key diff is correct
-            // and minimal, as before
-            common_keys = std::move(common_keys_source_order);
-            return true;
-        }
-
-        // slow path: the common keys are in a different relative
-        // order in source and target (only possible for a
-        // reorderable object_t like ordered_map). Building a
-        // minimal reordering patch is a nontrivial (LCS-like)
-        // problem; instead, remove every source key -- both
-        // deleted keys (which must be removed regardless) and
-        // common keys (removed so they can be re-added in
-        // target's order) -- and re-add every key that should
-        // remain, with its final target value, in target's
-        // order. basic_json::patch()'s "add" operation on an
-        // object uses operator[], which appends at the end for a
-        // vector-backed insertion-ordered map when the key does
-        // not already exist -- so removing a key and then adding
-        // it moves it to the end, fixing its position.
-        for (auto it = source.cbegin(); it != source.cend(); ++it)
-        {
-            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
-        }
-
-        // add every key that is either common (just removed
-        // above) or brand new, in target's iteration order, so
-        // that the final order after applying the patch matches
-        // target exactly
-        for (auto it = target.cbegin(); it != target.cend(); ++it)
-        {
-            diff_add(result, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
-        }
-        return false;
-    }
-
-    /*!
-    @brief @ref diff, for values at nesting level @a depth, appending the
-           operations to @a result
-
-    Diffing two arrays or objects calls this function again, once per nesting
-    level, so values nested deeply enough used to exhaust the call stack and
-    terminate the process. The descent is bounded here: once @ref
-    detail::recursion_depth_limit levels have been entered, @ref
-    diff_iteratively diffs what is left without the call stack.
-    */
-    static void diff_recursively(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path, const std::size_t depth)
-    {
-        // if the values are the same, there is nothing to do
+        // if the values are the same, return an empty patch
         if (source == target)
         {
-            return;
-        }
-
-        if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
-        {
-            diff_iteratively(result, source, target, path);
-            return;
+            return result;
         }
 
         if (source.type() != target.type())
         {
             // different types: replace value
-            diff_replace(result, path, target);
-            return;
+            result.push_back(
+            {
+                {"op", "replace"}, {"path", path}, {"value", target}
+            });
+            return result;
         }
 
         switch (source.type())
@@ -6367,50 +6152,200 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                 while (i < source.size() && i < target.size())
                 {
                     // recursive call to compare array values at index i
-                    diff_recursively(result, source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)), depth + 1);
+                    auto temp_diff = diff(source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)));
+                    result.insert(result.end(), temp_diff.begin(), temp_diff.end());
                     ++i;
                 }
 
                 // We now reached the end of at least one array
                 // in a second pass, traverse the remaining elements
-                diff_array_tails(result, source, target, path, i);
+
+                // remove my remaining elements, highest index first; appending
+                // in that order avoids the quadratic reinsertion done before
+                for (std::size_t j = source.size(); j > i; --j)
+                {
+                    result.push_back(object(
+                    {
+                        {"op", "remove"},
+                        {"path", detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1))}
+                    }));
+                }
+                i = source.size();
+
+                // add other remaining elements
+                while (i < target.size())
+                {
+                    result.push_back(
+                    {
+                        {"op", "add"},
+                        {"path", detail::concat<string_t>(path, "/-")},
+                        {"value", target[i]}
+                    });
+                    ++i;
+                }
+
                 break;
             }
 
             case value_t::object:
             {
-                std::vector<typename object_t::key_type> common_keys;
-                basic_json added_ops(value_t::array);
-                if (diff_object_keys(result, source, target, path, common_keys, added_ops))
+                // first pass: record, for every source key, whether it is
+                // common to both objects (in source's iteration order) or
+                // was deleted (i.e., in source but not in target) -- this is
+                // a by-product of the target.find() call already needed to
+                // tell the two cases apart, so it adds no extra lookups. The
+                // "remove" ops themselves are emitted later, interleaved
+                // with the recursive per-key diffs in the fast path below,
+                // to match source's original iteration order (as the
+                // original, pre-reordering-aware implementation did) instead
+                // of grouping all removes before all recursive diffs.
+                std::vector<typename object_t::key_type> common_keys_source_order;
+                for (auto it = source.cbegin(); it != source.cend(); ++it)
                 {
-                    // fast path: common_keys is, by construction, the
-                    // subsequence of source's keys that are common to both
-                    // objects, in source's iteration order -- so it can be
-                    // walked in lockstep with `source` using a cheap key
-                    // comparison instead of another lookup. Deleted keys
-                    // (those source keys not in common_keys) are interleaved
-                    // here too, in source's original order, to match the
-                    // historical (pre-reordering-aware) output order.
-                    auto common_it = common_keys.cbegin();
+                    if (target.find(it.key()) != target.end())
+                    {
+                        common_keys_source_order.push_back(it.key());
+                    }
+                }
+
+                // second pass: find keys that were added (i.e., in target but
+                // not in source), and record the keys common to both, in
+                // target's iteration order -- again a by-product of the
+                // source.find() call already needed to detect added keys. At
+                // the same time, determine whether every added key comes
+                // after every common key in target's order (a precondition
+                // for the fast path below, which only ever appends new keys
+                // at the very end). Both are only needed for an object_t that
+                // keeps its members in insertion order, such as the one
+                // backing `ordered_json`; for any other object_t, the fast
+                // path is always taken and they are not computed.
+                // patch ops for keys that were added (i.e., in target but not
+                // in source); built here so the fast path below can reuse
+                // them without a second source.find() per target key. Only
+                // used by the fast path -- the slow (reordering) path
+                // rebuilds "add" ops for every key itself.
+                std::vector<typename object_t::key_type> common_keys_target_order;
+                basic_json added_ops(value_t::array);
+                bool new_keys_form_suffix = true;
+                bool seen_new_key = false;
+                for (auto it = target.cbegin(); it != target.cend(); ++it)
+                {
+                    if (source.find(it.key()) == source.end())
+                    {
+                        seen_new_key = true;
+                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                        added_ops.push_back(
+                        {
+                            {"op", "add"}, {"path", path_key},
+                            {"value", it.value()}
+                        });
+                    }
+                    else
+                    {
+#ifdef JSON_HEDLEY_MSVC_VERSION
+#pragma warning(push )
+#pragma warning(disable : 4127) // ignore warning to replace if with if constexpr
+#endif
+                        if (detail::is_ordered_map<object_t>::value)
+                        {
+                            common_keys_target_order.push_back(it.key());
+                            if (seen_new_key)
+                            {
+                                new_keys_form_suffix = false;
+                            }
+                        }
+#ifdef JSON_HEDLEY_MSVC_VERSION
+#pragma warning( pop )
+#endif
+                    }
+                }
+
+                // Only an object type that keeps its members in insertion
+                // order, such as nlohmann::ordered_map, can need reordering:
+                // patch() appends a new member at the end of such an object.
+                // Any other object type places its members itself - std::map
+                // in key order, a hash map in an order its operator== ignores -
+                // so a member-by-member diff always reproduces target there.
+                if (!detail::is_ordered_map<object_t>::value
+                        || (common_keys_source_order == common_keys_target_order && new_keys_form_suffix))
+                {
+                    // fast path: order of common keys already matches (or the
+                    // object_t's iteration order does not depend on
+                    // insertion history), so a plain per-key recursive diff
+                    // is correct and minimal, as before. common_keys_source_order
+                    // is, by construction, the subsequence of source's keys
+                    // that are common to both objects, in source's iteration
+                    // order -- so it can be walked in lockstep with `source`
+                    // using a cheap key comparison instead of another lookup.
+                    // Deleted keys (those source keys not in common_keys_source_order)
+                    // are interleaved here too, in source's original order, to
+                    // match the historical (pre-reordering-aware) output order.
+                    auto common_it = common_keys_source_order.cbegin();
                     for (auto it = source.cbegin(); it != source.cend(); ++it)
                     {
-                        if (common_it != common_keys.cend() && it.key() == *common_it)
+                        if (common_it != common_keys_source_order.cend() && it.key() == *common_it)
                         {
-                            diff_recursively(result, it.value(), target[it.key()], detail::concat<string_t>(path, '/', detail::escape(it.key())), depth + 1);
+                            const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                            auto temp_diff = diff(it.value(), target[it.key()], path_key);
+                            result.insert(result.end(), temp_diff.begin(), temp_diff.end());
                             ++common_it;
                         }
                         else
                         {
                             // found a key that is not in target -> remove it
-                            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
+                            const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                            result.push_back(object(
+                            {
+                                {"op", "remove"}, {"path", path_key}
+                            }));
                         }
                     }
 
-                    // append the "add" ops for brand-new keys collected by
-                    // diff_object_keys -- no second source.find() per target
-                    // key needed
+                    // append the "add" ops for brand-new keys collected above
+                    // during the pass over target -- no second source.find()
+                    // per target key needed
                     result.insert(result.end(), added_ops.begin(), added_ops.end());
                 }
+                else
+                {
+                    // slow path: the common keys are in a different relative
+                    // order in source and target (only possible for a
+                    // reorderable object_t like ordered_map). Building a
+                    // minimal reordering patch is a nontrivial (LCS-like)
+                    // problem; instead, remove every source key -- both
+                    // deleted keys (which must be removed regardless) and
+                    // common keys (removed so they can be re-added in
+                    // target's order) -- and re-add every key that should
+                    // remain, with its final target value, in target's
+                    // order. basic_json::patch()'s "add" operation on an
+                    // object uses operator[], which appends at the end for a
+                    // vector-backed insertion-ordered map when the key does
+                    // not already exist -- so removing a key and then adding
+                    // it moves it to the end, fixing its position.
+                    for (auto it = source.cbegin(); it != source.cend(); ++it)
+                    {
+                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                        result.push_back(object(
+                        {
+                            {"op", "remove"}, {"path", path_key}
+                        }));
+                    }
+
+                    // add every key that is either common (just removed
+                    // above) or brand new, in target's iteration order, so
+                    // that the final order after applying the patch matches
+                    // target exactly
+                    for (auto it = target.cbegin(); it != target.cend(); ++it)
+                    {
+                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                        result.push_back(
+                        {
+                            {"op", "add"}, {"path", path_key},
+                            {"value", it.value()}
+                        });
+                    }
+                }
+
                 break;
             }
 
@@ -6425,170 +6360,16 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             default:
             {
                 // both primitive types: replace value
-                diff_replace(result, path, target);
+                result.push_back(
+                {
+                    {"op", "replace"}, {"path", path}, {"value", target}
+                });
                 break;
             }
         }
+
+        return result;
     }
-
-    /*!
-    @brief @ref diff without the call stack, appending the operations to
-           @a result
-
-    Produces the same operations as @ref diff_recursively. Only reached for
-    values nested more deeply than @ref detail::recursion_depth_limit.
-    */
-    static void diff_iteratively(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path)
-    {
-        // The arrays and objects being diffed are kept on an explicit stack,
-        // and every pair of elements is still diffed completely before the
-        // next one, so the operations come out in the same order as in
-        // diff_recursively. The path of the values being diffed is kept in
-        // one buffer that grows and shrinks with the stack, rather than in a
-        // new string per level.
-        std::vector<diff_frame> stack;
-        string_t current_path = path;
-
-        // diff `s` against `t`, whose path is current_path: primitives,
-        // values of different types, and objects whose members were reordered
-        // are handled right away; arrays and other objects get a frame
-        const auto enter = [&result, &stack, &current_path](const basic_json & s, const basic_json & t)
-        {
-            // if the values are the same, there is nothing to do. Arrays and
-            // objects are not compared up front: comparing them visits
-            // everything below them, so doing that at every level would take
-            // quadratic time in the nesting depth - equal ones yield no
-            // operations anyway.
-            if ((!s.is_structured() || !t.is_structured()) && s == t)
-            {
-                return;
-            }
-
-            if (s.type() != t.type())
-            {
-                // different types: replace value
-                diff_replace(result, current_path, t);
-                return;
-            }
-
-            switch (s.type())
-            {
-                case value_t::array:
-                {
-                    stack.emplace_back(&s, &t, current_path.size());
-                    return;
-                }
-
-                case value_t::object:
-                {
-                    std::vector<typename object_t::key_type> common_keys;
-                    basic_json added_ops(value_t::array);
-                    if (diff_object_keys(result, s, t, current_path, common_keys, added_ops))
-                    {
-                        // fast path: the frame walks source in lockstep with
-                        // common_keys, as diff_recursively does, and appends
-                        // added_ops once all members are done
-                        stack.emplace_back(&s, &t, current_path.size());
-                        stack.back().member = s.cbegin();
-                        stack.back().common_keys = std::move(common_keys);
-                        stack.back().added_ops = std::move(added_ops);
-                    }
-                    return;
-                }
-
-                case value_t::null:
-                case value_t::string:
-                case value_t::boolean:
-                case value_t::number_integer:
-                case value_t::number_unsigned:
-                case value_t::number_float:
-                case value_t::binary:
-                case value_t::discarded:
-                default:
-                {
-                    // both primitive types: replace value
-                    diff_replace(result, current_path, t);
-                    return;
-                }
-            }
-        };
-
-        enter(source, target);
-        while (!stack.empty())
-        {
-            // the frame is copied out member by member and changed through
-            // stack.back(): enter() may push a frame and the end of the loop
-            // pops it, either of which would invalidate a reference to it
-            const basic_json* const s = stack.back().source;
-            const basic_json* const t = stack.back().target;
-            const std::size_t path_length = stack.back().path_length;
-            const std::size_t depth = stack.size();
-
-            if (s->is_array())
-            {
-                const auto& source_array = *s->m_data.m_value.array;
-                const auto& target_array = *t->m_data.m_value.array;
-
-                // first pass: traverse common elements
-                const std::size_t i = stack.back().index;
-                if (i < source_array.size() && i < target_array.size())
-                {
-                    ++stack.back().index;
-                    detail::concat_into(current_path, '/', detail::to_string<string_t>(i));
-                    enter(source_array[i], target_array[i]);
-                    if (stack.size() == depth)
-                    {
-                        current_path.resize(path_length);
-                    }
-                    continue;
-                }
-
-                // We now reached the end of at least one array
-                // in a second pass, traverse the remaining elements
-                diff_array_tails(result, *s, *t, current_path, i);
-            }
-            else
-            {
-                const const_iterator it = stack.back().member;
-                if (it != s->cend())
-                {
-                    ++stack.back().member;
-                    const std::size_t next_common = stack.back().next_common;
-                    if (next_common < stack.back().common_keys.size() && it.key() == stack.back().common_keys[next_common])
-                    {
-                        ++stack.back().next_common;
-                        const basic_json& target_value = (*t)[it.key()];
-                        detail::concat_into(current_path, '/', detail::escape(it.key()));
-                        enter(it.value(), target_value);
-                        if (stack.size() == depth)
-                        {
-                            current_path.resize(path_length);
-                        }
-                    }
-                    else
-                    {
-                        // found a key that is not in target -> remove it
-                        diff_remove(result, detail::concat<string_t>(current_path, '/', detail::escape(it.key())));
-                    }
-                    continue;
-                }
-
-                // append the "add" ops for brand-new keys collected when the
-                // object was entered
-                result.insert(result.end(), stack.back().added_ops.begin(), stack.back().added_ops.end());
-            }
-
-            // this array or object is done: continue with the one it is in
-            stack.pop_back();
-            if (!stack.empty())
-            {
-                current_path.resize(stack.back().path_length);
-            }
-        }
-    }
-
-  public:
     /// @}
 
     ////////////////////////////////

single_include/nlohmann/json.hpp

@@ -4756,6 +4756,30 @@ using is_usable_as_key_type = typename std::conditional <
                               std::true_type,
                               std::false_type >::type;
 
+#ifdef JSON_HAS_CPP_17
+// type trait to check if KeyType can only be used as an object key after
+// converting it to std::string_view: it is convertible to std::string_view, the
+// object's comparator cannot compare it with object_t::key_type directly, but
+// can compare a std::string_view. JSON pointers and JSON iterators are ruled out
+// first, so that the conversion checks are never instantiated for them (a JSON
+// pointer's deprecated conversion to string_t would be named otherwise).
+template < typename BasicJsonType, typename KeyTypeCVRef, typename KeyType = uncvref_t<KeyTypeCVRef>,
+           bool = is_json_pointer<KeyType>::value || is_json_iterator_of<BasicJsonType, KeyType>::value >
+struct is_string_view_convertible_key_type : std::false_type {};
+
+template<typename BasicJsonType, typename KeyTypeCVRef, typename KeyType>
+struct is_string_view_convertible_key_type<BasicJsonType, KeyTypeCVRef, KeyType, false>
+    : std::integral_constant < bool,
+      std::is_convertible<KeyTypeCVRef, std::string_view>::value
+      && !is_usable_as_key_type<typename BasicJsonType::object_comparator_t,
+      typename BasicJsonType::object_t::key_type, KeyTypeCVRef, true, false>::value
+      && is_usable_as_key_type<typename BasicJsonType::object_comparator_t,
+      typename BasicJsonType::object_t::key_type, std::string_view, true, false>::value > {};
+#else
+template<typename BasicJsonType, typename KeyTypeCVRef>
+struct is_string_view_convertible_key_type : std::false_type {};
+#endif
+
 // type trait to check if KeyType can be used as an object key
 // true if:
 //   - KeyType is comparable with BasicJsonType::object_t::key_type
@@ -4769,9 +4793,7 @@ using is_usable_as_basic_json_key_type = typename std::conditional <
      typename BasicJsonType::object_t::key_type, KeyTypeCVRef,
      RequireTransparentComparator, ExcludeObjectKeyType>::value
      && !is_json_iterator_of<BasicJsonType, KeyType>::value)
-#ifdef JSON_HAS_CPP_17
-    || std::is_convertible<KeyType, std::string_view>::value
-#endif
+    || is_string_view_convertible_key_type<BasicJsonType, KeyTypeCVRef>::value
     , std::true_type,
     std::false_type >::type;
 
@@ -27734,6 +27756,24 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         return it;
     }
 
+    /// @brief the key to look up an object member with: the key itself, or its
+    ///        std::string_view if the object can only be searched with that
+    template < typename KeyType, detail::enable_if_t <
+                   !detail::is_string_view_convertible_key_type<basic_json_t, KeyType>::value, int > = 0 >
+    static KeyType && lookup_key(KeyType && key) noexcept
+    {
+        return std::forward<KeyType>(key);
+    }
+
+#ifdef JSON_HAS_CPP_17
+    template < typename KeyType, detail::enable_if_t <
+                   detail::is_string_view_convertible_key_type<basic_json_t, KeyType>::value, int > = 0 >
+    static std::string_view lookup_key(KeyType && key)
+    {
+        return std::forward<KeyType>(key);
+    }
+#endif
+
     /// @brief erase an element from the object and return the following one
     /// Not every map returns an iterator from erase(iterator): some containers
     /// (e.g., Abseil's hash maps) return void to avoid computing a successor
@@ -29694,7 +29734,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             JSON_THROW(type_error::create(304, detail::concat("cannot use at() with ", type_name()), this));
         }
 
-        auto it = m_data.m_value.object->find(std::forward<KeyType>(key));
+        auto it = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         if (it == m_data.m_value.object->end())
         {
             JSON_THROW(out_of_range::create(403, detail::concat("key '", string_t(std::forward<KeyType>(key)), "' not found"), this));
@@ -29732,7 +29772,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             JSON_THROW(type_error::create(304, detail::concat("cannot use at() with ", type_name()), this));
         }
 
-        auto it = m_data.m_value.object->find(std::forward<KeyType>(key));
+        auto it = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         if (it == m_data.m_value.object->end())
         {
             JSON_THROW(out_of_range::create(403, detail::concat("key '", string_t(std::forward<KeyType>(key)), "' not found"), this));
@@ -29875,7 +29915,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // operator[] only works for objects
         if (JSON_HEDLEY_LIKELY(is_object()))
         {
-            auto result = m_data.m_value.object->emplace(std::forward<KeyType>(key), nullptr);
+            auto result = m_data.m_value.object->emplace(lookup_key(std::forward<KeyType>(key)), nullptr);
             return set_parent(result.first->second);
         }
 
@@ -29891,7 +29931,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // const operator[] only works for objects
         if (JSON_HEDLEY_LIKELY(is_object()))
         {
-            auto it = m_data.m_value.object->find(std::forward<KeyType>(key));
+            auto it = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
             JSON_ASSERT(it != m_data.m_value.object->end());
             return it->second;
         }
@@ -29901,8 +29941,10 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
   private:
     template<typename KeyType>
-    using is_comparable_with_object_key = detail::is_comparable <
-        object_comparator_t, const typename object_t::key_type&, KeyType >;
+    using is_comparable_with_object_key = std::integral_constant < bool,
+        detail::is_comparable <
+            object_comparator_t, const typename object_t::key_type&, KeyType >::value
+        || detail::is_string_view_convertible_key_type<basic_json_t, KeyType>::value >;
 
     template<typename ValueType>
     using value_return_type = std::conditional <
@@ -30289,7 +30331,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             JSON_THROW(type_error::create(307, detail::concat("cannot use erase() with ", type_name()), this));
         }
 
-        const auto it = m_data.m_value.object->find(std::forward<KeyType>(key));
+        const auto it = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         if (it != m_data.m_value.object->end())
         {
             m_data.m_value.object->erase(it);
@@ -30316,7 +30358,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                  detail::is_usable_as_basic_json_key_type<basic_json_t, KeyType>::value, int> = 0>
     size_type erase(KeyType && key)
     {
-        return erase_internal(std::forward<KeyType>(key));
+        return erase_internal(lookup_key(std::forward<KeyType>(key)));
     }
 
     /// @brief remove element from a JSON array given an index
@@ -30396,7 +30438,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
         if (is_object())
         {
-            result.m_it.object_iterator = m_data.m_value.object->find(std::forward<KeyType>(key));
+            result.m_it.object_iterator = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         }
 
         return result;
@@ -30412,7 +30454,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
         if (is_object())
         {
-            result.m_it.object_iterator = m_data.m_value.object->find(std::forward<KeyType>(key));
+            result.m_it.object_iterator = m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
         }
 
         return result;
@@ -30435,7 +30477,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     size_type count(KeyType && key) const
     {
         // return 0 for all nonobject types
-        return is_object() ? m_data.m_value.object->count(std::forward<KeyType>(key)) : 0;
+        return is_object() ? m_data.m_value.object->count(lookup_key(std::forward<KeyType>(key))) : 0;
     }
 
     /// @brief check the existence of an element in a JSON object
@@ -30453,7 +30495,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     JSON_HEDLEY_WARN_UNUSED_RESULT
     bool contains(KeyType && key) const
     {
-        return is_object() && m_data.m_value.object->find(std::forward<KeyType>(key)) != m_data.m_value.object->end();
+        return is_object() && m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key))) != m_data.m_value.object->end();
     }
 
     /// @brief check the existence of an element in a JSON object given a JSON pointer
@@ -33033,256 +33075,21 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     {
         // the patch
         basic_json result(value_t::array);
-        diff_recursively(result, source, target, path, 0);
-        return result;
-    }
 
-  private:
-    /// @brief two arrays or two objects @ref diff_iteratively is diffing
-    struct diff_frame
-    {
-        diff_frame(const basic_json* source_, const basic_json* target_, const std::size_t path_length_) noexcept
-            : source(source_), target(target_), path_length(path_length_)
-        {}
-
-        // declared for GCC's -Weffc++, which asks for them in a class with
-        // pointer members and a non-trivial destructor; the exception
-        // specifications are left implicit, as GCC 4.8 rejects explicit ones
-        // that differ from them
-        diff_frame(const diff_frame&) = default;
-        diff_frame(diff_frame&&) = default;
-        diff_frame& operator=(const diff_frame&) = default;
-        diff_frame& operator=(diff_frame&&) = default;
-        ~diff_frame() = default;
-
-        /// the values being diffed, both arrays or both objects
-        const basic_json* source;
-        const basic_json* target;
-        /// the length of their path in `current_path`
-        std::size_t path_length;
-        /// arrays: the next index to diff
-        std::size_t index = 0;
-        /// objects: the next member of source to look at
-        const_iterator member{}; // NOLINT(readability-redundant-member-init)
-        /// objects: the keys common to both, in source's order
-        std::vector<typename object_t::key_type> common_keys{}; // NOLINT(readability-redundant-member-init)
-        /// objects: the next entry of common_keys
-        std::size_t next_common = 0;
-        /// objects: the "add" operations for keys only target has
-        basic_json added_ops{}; // NOLINT(readability-redundant-member-init)
-    };
-
-    // The operations of a diff are built by the functions below rather than
-    // where they are needed: building one takes several temporaries, and
-    // unoptimized builds give each temporary a stack slot of its own in the
-    // function it appears in. In diff_recursively, which is on the call stack
-    // once per nesting level, that made every level cost kilobytes of stack.
-
-    /// @brief append a "replace" operation for @a path with @a value to @a result
-    static void diff_replace(basic_json& result, const string_t& path, const basic_json& value)
-    {
-        result.push_back(
-        {
-            {"op", "replace"}, {"path", path}, {"value", value}
-        });
-    }
-
-    /// @brief append a "remove" operation for @a path to @a result
-    static void diff_remove(basic_json& result, const string_t& path)
-    {
-        result.push_back(object(
-        {
-            {"op", "remove"}, {"path", path}
-        }));
-    }
-
-    /// @brief append an "add" operation for @a path with @a value to @a result
-    static void diff_add(basic_json& result, const string_t& path, const basic_json& value)
-    {
-        result.push_back(
-        {
-            {"op", "add"}, {"path", path}, {"value", value}
-        });
-    }
-
-    /// @brief append the "remove" operations for the elements of array
-    ///        @a source from @a index on, and the "add" operations for the
-    ///        elements of array @a target from source's size on, to @a result
-    static void diff_array_tails(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path, const std::size_t index)
-    {
-        // remove my remaining elements, highest index first; appending
-        // in that order avoids the quadratic reinsertion done before
-        for (std::size_t j = source.size(); j > index; --j)
-        {
-            diff_remove(result, detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1)));
-        }
-
-        // add other remaining elements
-        for (std::size_t i = source.size(); i < target.size(); ++i)
-        {
-            diff_add(result, detail::concat<string_t>(path, "/-"), target[i]);
-        }
-    }
-
-    /*!
-    @brief compare the keys of objects @a source and @a target
-
-    If object_t does not keep its members in insertion order, or if the keys
-    both objects have are in the same order in both, and the keys only
-    @a target has come after them, stores the keys common to both in
-    source's order in @a common_keys, stores the "add" operations for the keys
-    only @a target has in @a added_ops, and returns true: the caller then diffs
-    the objects member by member. Otherwise, appends operations that remove
-    every member of @a source and add every member of @a target to @a result,
-    and returns false.
-    */
-    static bool diff_object_keys(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path, std::vector<typename object_t::key_type>& common_keys,
-                                 basic_json& added_ops)
-    {
-        // first pass: record, for every source key, whether it is
-        // common to both objects (in source's iteration order) or
-        // was deleted (i.e., in source but not in target) -- this is
-        // a by-product of the target.find() call already needed to
-        // tell the two cases apart, so it adds no extra lookups. The
-        // "remove" ops themselves are emitted later, interleaved
-        // with the per-key diffs in the caller's fast path, to match
-        // source's original iteration order (as the original,
-        // pre-reordering-aware implementation did) instead of
-        // grouping all removes before all per-key diffs.
-        std::vector<typename object_t::key_type> common_keys_source_order;
-        for (auto it = source.cbegin(); it != source.cend(); ++it)
-        {
-            if (target.find(it.key()) != target.end())
-            {
-                common_keys_source_order.push_back(it.key());
-            }
-        }
-
-        // second pass: find keys that were added (i.e., in target but
-        // not in source), and record the keys common to both, in
-        // target's iteration order -- again a by-product of the
-        // source.find() call already needed to detect added keys. At
-        // the same time, determine whether every added key comes
-        // after every common key in target's order (a precondition
-        // for the fast path, which only ever appends new keys
-        // at the very end). Both are only needed for an object_t that
-        // keeps its members in insertion order, such as the one
-        // backing `ordered_json`; for any other object_t, the fast
-        // path is always taken and they are not computed.
-        // The patch ops for keys that were added (i.e., in target but not
-        // in source) are built here so the fast path can reuse
-        // them without a second source.find() per target key. Only
-        // used by the fast path -- the slow (reordering) path
-        // rebuilds "add" ops for every key itself.
-        std::vector<typename object_t::key_type> common_keys_target_order;
-        bool new_keys_form_suffix = true;
-        bool seen_new_key = false;
-        for (auto it = target.cbegin(); it != target.cend(); ++it)
-        {
-            if (source.find(it.key()) == source.end())
-            {
-                seen_new_key = true;
-                diff_add(added_ops, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
-            }
-            else
-            {
-#ifdef JSON_HEDLEY_MSVC_VERSION
-#pragma warning(push )
-#pragma warning(disable : 4127) // ignore warning to replace if with if constexpr
-#endif
-                if (detail::is_ordered_map<object_t>::value)
-                {
-                    common_keys_target_order.push_back(it.key());
-                    if (seen_new_key)
-                    {
-                        new_keys_form_suffix = false;
-                    }
-                }
-#ifdef JSON_HEDLEY_MSVC_VERSION
-#pragma warning( pop )
-#endif
-            }
-        }
-
-        // Only an object type that keeps its members in insertion
-        // order, such as nlohmann::ordered_map, can need reordering:
-        // patch() appends a new member at the end of such an object.
-        // Any other object type places its members itself - std::map
-        // in key order, a hash map in an order its operator== ignores -
-        // so a member-by-member diff always reproduces target there.
-        if (!detail::is_ordered_map<object_t>::value
-                || (common_keys_source_order == common_keys_target_order && new_keys_form_suffix))
-        {
-            // fast path: order of common keys already matches (or the
-            // object_t's iteration order does not depend on
-            // insertion history), so a plain per-key diff is correct
-            // and minimal, as before
-            common_keys = std::move(common_keys_source_order);
-            return true;
-        }
-
-        // slow path: the common keys are in a different relative
-        // order in source and target (only possible for a
-        // reorderable object_t like ordered_map). Building a
-        // minimal reordering patch is a nontrivial (LCS-like)
-        // problem; instead, remove every source key -- both
-        // deleted keys (which must be removed regardless) and
-        // common keys (removed so they can be re-added in
-        // target's order) -- and re-add every key that should
-        // remain, with its final target value, in target's
-        // order. basic_json::patch()'s "add" operation on an
-        // object uses operator[], which appends at the end for a
-        // vector-backed insertion-ordered map when the key does
-        // not already exist -- so removing a key and then adding
-        // it moves it to the end, fixing its position.
-        for (auto it = source.cbegin(); it != source.cend(); ++it)
-        {
-            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
-        }
-
-        // add every key that is either common (just removed
-        // above) or brand new, in target's iteration order, so
-        // that the final order after applying the patch matches
-        // target exactly
-        for (auto it = target.cbegin(); it != target.cend(); ++it)
-        {
-            diff_add(result, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
-        }
-        return false;
-    }
-
-    /*!
-    @brief @ref diff, for values at nesting level @a depth, appending the
-           operations to @a result
-
-    Diffing two arrays or objects calls this function again, once per nesting
-    level, so values nested deeply enough used to exhaust the call stack and
-    terminate the process. The descent is bounded here: once @ref
-    detail::recursion_depth_limit levels have been entered, @ref
-    diff_iteratively diffs what is left without the call stack.
-    */
-    static void diff_recursively(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path, const std::size_t depth)
-    {
-        // if the values are the same, there is nothing to do
+        // if the values are the same, return an empty patch
         if (source == target)
         {
-            return;
-        }
-
-        if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
-        {
-            diff_iteratively(result, source, target, path);
-            return;
+            return result;
         }
 
         if (source.type() != target.type())
         {
             // different types: replace value
-            diff_replace(result, path, target);
-            return;
+            result.push_back(
+            {
+                {"op", "replace"}, {"path", path}, {"value", target}
+            });
+            return result;
         }
 
         switch (source.type())
@@ -33294,50 +33101,200 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                 while (i < source.size() && i < target.size())
                 {
                     // recursive call to compare array values at index i
-                    diff_recursively(result, source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)), depth + 1);
+                    auto temp_diff = diff(source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)));
+                    result.insert(result.end(), temp_diff.begin(), temp_diff.end());
                     ++i;
                 }
 
                 // We now reached the end of at least one array
                 // in a second pass, traverse the remaining elements
-                diff_array_tails(result, source, target, path, i);
+
+                // remove my remaining elements, highest index first; appending
+                // in that order avoids the quadratic reinsertion done before
+                for (std::size_t j = source.size(); j > i; --j)
+                {
+                    result.push_back(object(
+                    {
+                        {"op", "remove"},
+                        {"path", detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1))}
+                    }));
+                }
+                i = source.size();
+
+                // add other remaining elements
+                while (i < target.size())
+                {
+                    result.push_back(
+                    {
+                        {"op", "add"},
+                        {"path", detail::concat<string_t>(path, "/-")},
+                        {"value", target[i]}
+                    });
+                    ++i;
+                }
+
                 break;
             }
 
             case value_t::object:
             {
-                std::vector<typename object_t::key_type> common_keys;
-                basic_json added_ops(value_t::array);
-                if (diff_object_keys(result, source, target, path, common_keys, added_ops))
+                // first pass: record, for every source key, whether it is
+                // common to both objects (in source's iteration order) or
+                // was deleted (i.e., in source but not in target) -- this is
+                // a by-product of the target.find() call already needed to
+                // tell the two cases apart, so it adds no extra lookups. The
+                // "remove" ops themselves are emitted later, interleaved
+                // with the recursive per-key diffs in the fast path below,
+                // to match source's original iteration order (as the
+                // original, pre-reordering-aware implementation did) instead
+                // of grouping all removes before all recursive diffs.
+                std::vector<typename object_t::key_type> common_keys_source_order;
+                for (auto it = source.cbegin(); it != source.cend(); ++it)
                 {
-                    // fast path: common_keys is, by construction, the
-                    // subsequence of source's keys that are common to both
-                    // objects, in source's iteration order -- so it can be
-                    // walked in lockstep with `source` using a cheap key
-                    // comparison instead of another lookup. Deleted keys
-                    // (those source keys not in common_keys) are interleaved
-                    // here too, in source's original order, to match the
-                    // historical (pre-reordering-aware) output order.
-                    auto common_it = common_keys.cbegin();
+                    if (target.find(it.key()) != target.end())
+                    {
+                        common_keys_source_order.push_back(it.key());
+                    }
+                }
+
+                // second pass: find keys that were added (i.e., in target but
+                // not in source), and record the keys common to both, in
+                // target's iteration order -- again a by-product of the
+                // source.find() call already needed to detect added keys. At
+                // the same time, determine whether every added key comes
+                // after every common key in target's order (a precondition
+                // for the fast path below, which only ever appends new keys
+                // at the very end). Both are only needed for an object_t that
+                // keeps its members in insertion order, such as the one
+                // backing `ordered_json`; for any other object_t, the fast
+                // path is always taken and they are not computed.
+                // patch ops for keys that were added (i.e., in target but not
+                // in source); built here so the fast path below can reuse
+                // them without a second source.find() per target key. Only
+                // used by the fast path -- the slow (reordering) path
+                // rebuilds "add" ops for every key itself.
+                std::vector<typename object_t::key_type> common_keys_target_order;
+                basic_json added_ops(value_t::array);
+                bool new_keys_form_suffix = true;
+                bool seen_new_key = false;
+                for (auto it = target.cbegin(); it != target.cend(); ++it)
+                {
+                    if (source.find(it.key()) == source.end())
+                    {
+                        seen_new_key = true;
+                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                        added_ops.push_back(
+                        {
+                            {"op", "add"}, {"path", path_key},
+                            {"value", it.value()}
+                        });
+                    }
+                    else
+                    {
+#ifdef JSON_HEDLEY_MSVC_VERSION
+#pragma warning(push )
+#pragma warning(disable : 4127) // ignore warning to replace if with if constexpr
+#endif
+                        if (detail::is_ordered_map<object_t>::value)
+                        {
+                            common_keys_target_order.push_back(it.key());
+                            if (seen_new_key)
+                            {
+                                new_keys_form_suffix = false;
+                            }
+                        }
+#ifdef JSON_HEDLEY_MSVC_VERSION
+#pragma warning( pop )
+#endif
+                    }
+                }
+
+                // Only an object type that keeps its members in insertion
+                // order, such as nlohmann::ordered_map, can need reordering:
+                // patch() appends a new member at the end of such an object.
+                // Any other object type places its members itself - std::map
+                // in key order, a hash map in an order its operator== ignores -
+                // so a member-by-member diff always reproduces target there.
+                if (!detail::is_ordered_map<object_t>::value
+                        || (common_keys_source_order == common_keys_target_order && new_keys_form_suffix))
+                {
+                    // fast path: order of common keys already matches (or the
+                    // object_t's iteration order does not depend on
+                    // insertion history), so a plain per-key recursive diff
+                    // is correct and minimal, as before. common_keys_source_order
+                    // is, by construction, the subsequence of source's keys
+                    // that are common to both objects, in source's iteration
+                    // order -- so it can be walked in lockstep with `source`
+                    // using a cheap key comparison instead of another lookup.
+                    // Deleted keys (those source keys not in common_keys_source_order)
+                    // are interleaved here too, in source's original order, to
+                    // match the historical (pre-reordering-aware) output order.
+                    auto common_it = common_keys_source_order.cbegin();
                     for (auto it = source.cbegin(); it != source.cend(); ++it)
                     {
-                        if (common_it != common_keys.cend() && it.key() == *common_it)
+                        if (common_it != common_keys_source_order.cend() && it.key() == *common_it)
                         {
-                            diff_recursively(result, it.value(), target[it.key()], detail::concat<string_t>(path, '/', detail::escape(it.key())), depth + 1);
+                            const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                            auto temp_diff = diff(it.value(), target[it.key()], path_key);
+                            result.insert(result.end(), temp_diff.begin(), temp_diff.end());
                             ++common_it;
                         }
                         else
                         {
                             // found a key that is not in target -> remove it
-                            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
+                            const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                            result.push_back(object(
+                            {
+                                {"op", "remove"}, {"path", path_key}
+                            }));
                         }
                     }
 
-                    // append the "add" ops for brand-new keys collected by
-                    // diff_object_keys -- no second source.find() per target
-                    // key needed
+                    // append the "add" ops for brand-new keys collected above
+                    // during the pass over target -- no second source.find()
+                    // per target key needed
                     result.insert(result.end(), added_ops.begin(), added_ops.end());
                 }
+                else
+                {
+                    // slow path: the common keys are in a different relative
+                    // order in source and target (only possible for a
+                    // reorderable object_t like ordered_map). Building a
+                    // minimal reordering patch is a nontrivial (LCS-like)
+                    // problem; instead, remove every source key -- both
+                    // deleted keys (which must be removed regardless) and
+                    // common keys (removed so they can be re-added in
+                    // target's order) -- and re-add every key that should
+                    // remain, with its final target value, in target's
+                    // order. basic_json::patch()'s "add" operation on an
+                    // object uses operator[], which appends at the end for a
+                    // vector-backed insertion-ordered map when the key does
+                    // not already exist -- so removing a key and then adding
+                    // it moves it to the end, fixing its position.
+                    for (auto it = source.cbegin(); it != source.cend(); ++it)
+                    {
+                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                        result.push_back(object(
+                        {
+                            {"op", "remove"}, {"path", path_key}
+                        }));
+                    }
+
+                    // add every key that is either common (just removed
+                    // above) or brand new, in target's iteration order, so
+                    // that the final order after applying the patch matches
+                    // target exactly
+                    for (auto it = target.cbegin(); it != target.cend(); ++it)
+                    {
+                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                        result.push_back(
+                        {
+                            {"op", "add"}, {"path", path_key},
+                            {"value", it.value()}
+                        });
+                    }
+                }
+
                 break;
             }
 
@@ -33352,170 +33309,16 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             default:
             {
                 // both primitive types: replace value
-                diff_replace(result, path, target);
+                result.push_back(
+                {
+                    {"op", "replace"}, {"path", path}, {"value", target}
+                });
                 break;
             }
         }
+
+        return result;
     }
-
-    /*!
-    @brief @ref diff without the call stack, appending the operations to
-           @a result
-
-    Produces the same operations as @ref diff_recursively. Only reached for
-    values nested more deeply than @ref detail::recursion_depth_limit.
-    */
-    static void diff_iteratively(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path)
-    {
-        // The arrays and objects being diffed are kept on an explicit stack,
-        // and every pair of elements is still diffed completely before the
-        // next one, so the operations come out in the same order as in
-        // diff_recursively. The path of the values being diffed is kept in
-        // one buffer that grows and shrinks with the stack, rather than in a
-        // new string per level.
-        std::vector<diff_frame> stack;
-        string_t current_path = path;
-
-        // diff `s` against `t`, whose path is current_path: primitives,
-        // values of different types, and objects whose members were reordered
-        // are handled right away; arrays and other objects get a frame
-        const auto enter = [&result, &stack, &current_path](const basic_json & s, const basic_json & t)
-        {
-            // if the values are the same, there is nothing to do. Arrays and
-            // objects are not compared up front: comparing them visits
-            // everything below them, so doing that at every level would take
-            // quadratic time in the nesting depth - equal ones yield no
-            // operations anyway.
-            if ((!s.is_structured() || !t.is_structured()) && s == t)
-            {
-                return;
-            }
-
-            if (s.type() != t.type())
-            {
-                // different types: replace value
-                diff_replace(result, current_path, t);
-                return;
-            }
-
-            switch (s.type())
-            {
-                case value_t::array:
-                {
-                    stack.emplace_back(&s, &t, current_path.size());
-                    return;
-                }
-
-                case value_t::object:
-                {
-                    std::vector<typename object_t::key_type> common_keys;
-                    basic_json added_ops(value_t::array);
-                    if (diff_object_keys(result, s, t, current_path, common_keys, added_ops))
-                    {
-                        // fast path: the frame walks source in lockstep with
-                        // common_keys, as diff_recursively does, and appends
-                        // added_ops once all members are done
-                        stack.emplace_back(&s, &t, current_path.size());
-                        stack.back().member = s.cbegin();
-                        stack.back().common_keys = std::move(common_keys);
-                        stack.back().added_ops = std::move(added_ops);
-                    }
-                    return;
-                }
-
-                case value_t::null:
-                case value_t::string:
-                case value_t::boolean:
-                case value_t::number_integer:
-                case value_t::number_unsigned:
-                case value_t::number_float:
-                case value_t::binary:
-                case value_t::discarded:
-                default:
-                {
-                    // both primitive types: replace value
-                    diff_replace(result, current_path, t);
-                    return;
-                }
-            }
-        };
-
-        enter(source, target);
-        while (!stack.empty())
-        {
-            // the frame is copied out member by member and changed through
-            // stack.back(): enter() may push a frame and the end of the loop
-            // pops it, either of which would invalidate a reference to it
-            const basic_json* const s = stack.back().source;
-            const basic_json* const t = stack.back().target;
-            const std::size_t path_length = stack.back().path_length;
-            const std::size_t depth = stack.size();
-
-            if (s->is_array())
-            {
-                const auto& source_array = *s->m_data.m_value.array;
-                const auto& target_array = *t->m_data.m_value.array;
-
-                // first pass: traverse common elements
-                const std::size_t i = stack.back().index;
-                if (i < source_array.size() && i < target_array.size())
-                {
-                    ++stack.back().index;
-                    detail::concat_into(current_path, '/', detail::to_string<string_t>(i));
-                    enter(source_array[i], target_array[i]);
-                    if (stack.size() == depth)
-                    {
-                        current_path.resize(path_length);
-                    }
-                    continue;
-                }
-
-                // We now reached the end of at least one array
-                // in a second pass, traverse the remaining elements
-                diff_array_tails(result, *s, *t, current_path, i);
-            }
-            else
-            {
-                const const_iterator it = stack.back().member;
-                if (it != s->cend())
-                {
-                    ++stack.back().member;
-                    const std::size_t next_common = stack.back().next_common;
-                    if (next_common < stack.back().common_keys.size() && it.key() == stack.back().common_keys[next_common])
-                    {
-                        ++stack.back().next_common;
-                        const basic_json& target_value = (*t)[it.key()];
-                        detail::concat_into(current_path, '/', detail::escape(it.key()));
-                        enter(it.value(), target_value);
-                        if (stack.size() == depth)
-                        {
-                            current_path.resize(path_length);
-                        }
-                    }
-                    else
-                    {
-                        // found a key that is not in target -> remove it
-                        diff_remove(result, detail::concat<string_t>(current_path, '/', detail::escape(it.key())));
-                    }
-                    continue;
-                }
-
-                // append the "add" ops for brand-new keys collected when the
-                // object was entered
-                result.insert(result.end(), stack.back().added_ops.begin(), stack.back().added_ops.end());
-            }
-
-            // this array or object is done: continue with the one it is in
-            stack.pop_back();
-            if (!stack.empty())
-            {
-                current_path.resize(stack.back().path_length);
-            }
-        }
-    }
-
-  public:
     /// @}
 
     ////////////////////////////////

tests/src/unit-element_access2.cpp

@@ -1973,4 +1973,115 @@ TEST_CASE("operator[] with user-defined std::string_view-convertible types")
         }
     }
 }
+
+TEST_CASE("keys convertible to std::string_view work with all lookup functions (regression test for #5663)")
+{
+    // a key type convertible only to std::string_view: the case #4958 added
+    // support for, but only the non-const operator[] compiled with it
+    struct ViewKey
+    {
+        operator std::string_view() const
+        {
+            return "a";
+        }
+    };
+
+    // a key type convertible to both std::string and std::string_view: with
+    // 3.12.0, such a key worked with at, the const operator[], find, count and
+    // contains via the conversion to std::string; #4958 made the KeyType&&
+    // templates win overload resolution for it instead, and those then failed
+    struct DualKey
+    {
+        operator std::string() const
+        {
+            return "a";
+        }
+        operator std::string_view() const
+        {
+            return "a";
+        }
+    };
+
+    SECTION("nlohmann::json")
+    {
+        using json = nlohmann::json;
+
+        SECTION("ViewKey")
+        {
+            json j = {{"a", 1}};
+            const json& cj = j;
+
+            CHECK(j[ViewKey{}] == 1);
+            CHECK(cj[ViewKey{}] == 1);
+            CHECK(j.at(ViewKey{}) == 1);
+            CHECK(cj.at(ViewKey{}) == 1);
+            CHECK(j.find(ViewKey{}) != j.end());
+            CHECK(cj.find(ViewKey{}) != cj.end());
+            CHECK(j.count(ViewKey{}) == 1);
+            CHECK(j.contains(ViewKey{}));
+            CHECK(j.value(ViewKey{}, 0) == 1);
+            CHECK(j.erase(ViewKey{}) == 1);
+            CHECK(!j.contains("a"));
+        }
+
+        SECTION("DualKey")
+        {
+            json j = {{"a", 1}};
+            const json& cj = j;
+
+            CHECK(j[DualKey{}] == 1);
+            CHECK(cj[DualKey{}] == 1);
+            CHECK(j.at(DualKey{}) == 1);
+            CHECK(cj.at(DualKey{}) == 1);
+            CHECK(j.find(DualKey{}) != j.end());
+            CHECK(cj.find(DualKey{}) != cj.end());
+            CHECK(j.count(DualKey{}) == 1);
+            CHECK(j.contains(DualKey{}));
+            CHECK(j.value(DualKey{}, 0) == 1);
+            CHECK(j.erase(DualKey{}) == 1);
+            CHECK(!j.contains("a"));
+        }
+    }
+
+    SECTION("nlohmann::ordered_json")
+    {
+        using ordered_json = nlohmann::ordered_json;
+
+        SECTION("ViewKey")
+        {
+            ordered_json j = {{"a", 1}};
+            const ordered_json& cj = j;
+
+            CHECK(j[ViewKey{}] == 1);
+            CHECK(cj[ViewKey{}] == 1);
+            CHECK(j.at(ViewKey{}) == 1);
+            CHECK(cj.at(ViewKey{}) == 1);
+            CHECK(j.find(ViewKey{}) != j.end());
+            CHECK(cj.find(ViewKey{}) != cj.end());
+            CHECK(j.count(ViewKey{}) == 1);
+            CHECK(j.contains(ViewKey{}));
+            CHECK(j.value(ViewKey{}, 0) == 1);
+            CHECK(j.erase(ViewKey{}) == 1);
+            CHECK(!j.contains("a"));
+        }
+
+        SECTION("DualKey")
+        {
+            ordered_json j = {{"a", 1}};
+            const ordered_json& cj = j;
+
+            CHECK(j[DualKey{}] == 1);
+            CHECK(cj[DualKey{}] == 1);
+            CHECK(j.at(DualKey{}) == 1);
+            CHECK(cj.at(DualKey{}) == 1);
+            CHECK(j.find(DualKey{}) != j.end());
+            CHECK(cj.find(DualKey{}) != cj.end());
+            CHECK(j.count(DualKey{}) == 1);
+            CHECK(j.contains(DualKey{}));
+            CHECK(j.value(DualKey{}, 0) == 1);
+            CHECK(j.erase(DualKey{}) == 1);
+            CHECK(!j.contains("a"));
+        }
+    }
+}
 #endif

tests/src/unit-json_patch.cpp

@@ -15,65 +15,8 @@ using nlohmann::json;
 #endif
 
 #include <fstream>
-#include <string>
-#include <vector>
 #include "make_test_data_available.hpp"
 
-namespace
-{
-// alternating objects and arrays nested `depth` levels deep, with members that
-// depend on `variant` at some levels, so diffing two variants yields
-// operations on many levels: replacing the innermost value, adding, removing,
-// and (for ordered_json) reordering members, and changing array lengths
-template<typename BasicJsonType>
-BasicJsonType nested(const std::size_t depth, const int variant)
-{
-    BasicJsonType value = variant;
-    for (std::size_t i = 0; i < depth; ++i)
-    {
-        if (i % 2 == 0)
-        {
-            BasicJsonType object = BasicJsonType::object();
-            if ((i + static_cast<std::size_t>(variant)) % 7 == 0)
-            {
-                object["x"] = i;
-            }
-            if (variant == 2 && i % 11 == 0)
-            {
-                object["z"] = "z";
-            }
-            object["a"] = std::move(value);
-            if (variant == 1 && i % 5 == 0)
-            {
-                object["y"] = 1;
-            }
-            value = std::move(object);
-        }
-        else
-        {
-            BasicJsonType array = BasicJsonType::array({std::move(value)});
-            if ((i + static_cast<std::size_t>(variant)) % 3 == 0)
-            {
-                array.push_back(i);
-            }
-            value = std::move(array);
-        }
-    }
-    return value;
-}
-
-// a path of `depth` reference tokens, as nested() nests its values
-std::string nested_path(const std::size_t depth)
-{
-    std::string path;
-    for (std::size_t i = depth; i > 0; --i)
-    {
-        path += (i - 1) % 2 == 0 ? "/a" : "/0";
-    }
-    return path;
-}
-} // namespace
-
 TEST_CASE("JSON patch")
 {
     SECTION("examples from RFC 6902")
@@ -1809,102 +1752,6 @@ TEST_CASE("JSON patch - diff emits array removals in descending index order")
     }
 }
 
-TEST_CASE("JSON patch: diff of deeply nested values")
-{
-    SECTION("the diff reproduces the target at every depth")
-    {
-        // depths on either side of the nesting depth up to which diff()
-        // recurses (detail::recursion_depth_limit(), 128); not every depth up
-        // to 300, as the test would then time out under Valgrind
-        std::vector<std::size_t> depths;
-        for (std::size_t depth = 0; depth <= 16; ++depth)
-        {
-            depths.push_back(depth);
-        }
-        for (std::size_t depth = 120; depth <= 136; ++depth)
-        {
-            depths.push_back(depth);
-        }
-        depths.push_back(300);
-
-        for (const auto depth : depths)
-        {
-            CAPTURE(depth);
-            for (int from = 0; from < 3; ++from)
-            {
-                for (int to = 0; to < 3; ++to)
-                {
-                    CAPTURE(from);
-                    CAPTURE(to);
-                    const auto source = nested<json>(depth, from);
-                    const auto target = nested<json>(depth, to);
-                    const auto patch = json::diff(source, target);
-                    CHECK(source.patch(patch) == target);
-                    CHECK(patch.empty() == (from == to));
-
-                    const auto ordered_source = nested<nlohmann::ordered_json>(depth, from);
-                    const auto ordered_target = nested<nlohmann::ordered_json>(depth, to);
-                    CHECK(ordered_source.patch(nlohmann::ordered_json::diff(ordered_source, ordered_target)) == ordered_target);
-                }
-            }
-        }
-    }
-
-    SECTION("a difference only in the innermost value is one replace operation")
-    {
-        for (std::size_t depth = 0; depth <= 300; ++depth)
-        {
-            CAPTURE(depth);
-            json source = 1;
-            json target = 2;
-            for (std::size_t i = 0; i < depth; ++i)
-            {
-                source = i % 2 == 0 ? json::object({{"a", std::move(source)}}) : json::array({std::move(source)});
-                target = i % 2 == 0 ? json::object({{"a", std::move(target)}}) : json::array({std::move(target)});
-            }
-            CHECK(json::diff(source, target, "/root") == json::array({{{"op", "replace"}, {"path", "/root" + nested_path(depth)}, {"value", 2}}}));
-        }
-    }
-
-    SECTION("values nested too deeply for the call stack (#5393)")
-    {
-        // diff() used to recurse once per nesting level, and compared the
-        // values with operator== on every level. The values are only
-        // parsed and diffed, never copied or compared, since those recurse
-        // too.
-        const std::size_t depth = 100000;
-        for (const bool objects :
-                {
-                    false, true
-                })
-        {
-            CAPTURE(objects);
-            std::string source_text;
-            std::string target_text;
-            std::string equal_text;
-            std::string path;
-            for (std::size_t i = 0; i < depth; ++i)
-            {
-                source_text += objects ? "{\"a\":" : "[";
-                path += objects ? "/a" : "/0";
-            }
-            target_text = source_text + "2";
-            equal_text = source_text + "1";
-            source_text += "1";
-            const std::string closing(depth, objects ? '}' : ']');
-            const auto source = json::parse(source_text + closing);
-
-            const auto patch = json::diff(source, json::parse(target_text + closing));
-            REQUIRE(patch.size() == 1);
-            CHECK(patch[0]["op"] == "replace");
-            CHECK(patch[0]["path"] == path);
-            CHECK(patch[0]["value"] == 2);
-
-            CHECK(json::diff(source, json::parse(equal_text + closing)).empty());
-        }
-    }
-}
-
 TEST_CASE("JSON patch - diff() takes the fast path for non-reorderable object types (regression #5639)")
 {
     // #5465 added an order check to diff()'s object handling so a