Throw when JSON Patch remove's target path resolves through a primitive or null parent

RFC 6902 (section 4.2) requires the target location of a "remove"
operation to exist. operation_remove handled parent.is_object() and
parent.is_array(), but had no final else branch: when the resolved
parent was a primitive value or null, neither branch matched and the
operation silently did nothing instead of failing.

Add the missing else branch, throwing out_of_range.413 with wording
that matches the existing out_of_range.411 thrown by the analogous
"add" case (operation_add) for the same kind of invalid parent.

Fixes #5396.

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

docs/mkdocs/docs/api/basic_json/patch.md

@@ -34,6 +34,8 @@ Strong guarantee: if an exception is thrown, there are no changes in the JSON va
   ("add", "remove", "move")
 - Throws [`out_of_range.411`](../../home/exceptions.md#jsonexceptionout_of_range411) if an "add" operation's target
   location has a parent that is neither an object nor an array.
+- Throws [`out_of_range.413`](../../home/exceptions.md#jsonexceptionout_of_range413) if a "remove" operation's target
+  location has a parent that is neither an object nor an array.
 - Throws [`other_error.501`](../../home/exceptions.md#jsonexceptionother_error501) if "test" operation was
   unsuccessful.
 
@@ -75,3 +77,5 @@ is thrown. In any case, the original value is not changed: the patch is applied
 - Added in version 2.0.0.
 - Added [`out_of_range.411`](../../home/exceptions.md#jsonexceptionout_of_range411) and stopped relying on an internal assertion when an "add" operation's
   target location has a non-object/non-array parent in version 3.13.0.
+- Added [`out_of_range.413`](../../home/exceptions.md#jsonexceptionout_of_range413) and stopped silently ignoring a "remove" operation whose target
+  location has a non-object/non-array parent in version 3.13.0.

docs/mkdocs/docs/api/basic_json/patch_inplace.md

@@ -30,6 +30,8 @@ No guarantees, value may be corrupted by an unsuccessful patch operation.
   ("add", "remove", "move")
 - Throws [`out_of_range.411`](../../home/exceptions.md#jsonexceptionout_of_range411) if an "add" operation's target
   location has a parent that is neither an object nor an array.
+- Throws [`out_of_range.413`](../../home/exceptions.md#jsonexceptionout_of_range413) if a "remove" operation's target
+  location has a parent that is neither an object nor an array.
 - Throws [`other_error.501`](../../home/exceptions.md#jsonexceptionother_error501) if "test" operation was
   unsuccessful.
 
@@ -72,3 +74,5 @@ function throws an exception.
 - Added in version 3.11.0.
 - Added [`out_of_range.411`](../../home/exceptions.md#jsonexceptionout_of_range411) and stopped relying on an internal assertion when an "add" operation's
   target location has a non-object/non-array parent in version 3.13.0.
+- Added [`out_of_range.413`](../../home/exceptions.md#jsonexceptionout_of_range413) and stopped silently ignoring a "remove" operation whose target
+  location has a non-object/non-array parent in version 3.13.0.

docs/mkdocs/docs/home/exceptions.md

@@ -933,6 +933,20 @@ BSON stores the length of documents, arrays, strings, and binary values in a sig
     [`to_bson`](../api/basic_json/to_bson.md) produced documents with negative length prefixes that
     [`from_bson`](../api/basic_json/from_bson.md) rejected.
 
+### json.exception.out_of_range.413
+
+A JSON Patch `remove` operation cannot be applied because the target location's parent is neither an object nor an array. Per [RFC 6902](https://datatracker.ietf.org/doc/html/rfc6902), a `remove` target must reference a member of an existing object or an element of an existing array; a primitive value (string, number, boolean, etc.) or `null` has no members or elements to remove.
+
+!!! failure "Example message"
+
+    ```
+    cannot remove value: the JSON Patch 'remove' target's parent is of type number, but must be an object or array
+    ```
+
+!!! note
+
+    This exception was added in version 3.13.0. Before that, this situation was silently ignored (the `remove` operation had no effect).
+
 ## Further exceptions
 
 This exception is thrown in case of errors that cannot be classified with the

include/nlohmann/detail/input/json_sax.hpp

@@ -8,11 +8,10 @@
 
 #pragma once
 
-#include <algorithm> // find_if
 #include <cstddef>
 #include <string> // string
 #include <type_traits> // enable_if_t
-#include <utility> // move, pair
+#include <utility> // move
 #include <vector> // vector
 
 #include <nlohmann/detail/exceptions.hpp>
@@ -250,7 +249,7 @@ class json_sax_dom_parser
 
         if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
         {
-            return parse_error(0, "", out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
+            JSON_THROW(out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
         }
 
         return true;
@@ -299,7 +298,7 @@ class json_sax_dom_parser
 
         if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
         {
-            return parse_error(0, "", out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
+            JSON_THROW(out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
         }
 
         return true;
@@ -569,7 +568,7 @@ class json_sax_dom_callback_parser
             // check object limit
             if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
             {
-                return parse_error(0, "", out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
+                JSON_THROW(out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
             }
         }
         return true;
@@ -586,17 +585,7 @@ class json_sax_dom_callback_parser
         // add discarded value at the given key and store the reference for later
         if (keep && ref_stack.back())
         {
-            auto& obj = *ref_stack.back()->m_data.m_value.object;
+            object_element = &(ref_stack.back()->m_data.m_value.object->operator[](val) = discarded);
-            const auto it = obj.find(val);
-            if (it != obj.end())
-            {
-                // this is a duplicate key (legal in JSON); remember its
-                // current value so it can be restored later if the new
-                // value is rejected by the callback, instead of being
-                // erased together with the discarded placeholder
-                duplicate_key_stash.emplace_back(&(it->second), it->second);
-            }
-            object_element = &(obj[val] = discarded);
         }
 
         return true;
@@ -608,18 +597,13 @@ class json_sax_dom_callback_parser
         {
             if (!callback(static_cast<int>(ref_stack.size()) - 1, parse_event_t::object_end, *ref_stack.back()))
             {
-                // discard object, unless this slot holds a duplicate key's
+                // discard object
-                // previous value pending restoration, in which case that
+                *ref_stack.back() = discarded;
-                // value is restored instead of being discarded
-                if (!resolve_duplicate_key_stash(ref_stack.back(), true))
-                {
-                    *ref_stack.back() = discarded;
 
 #if JSON_DIAGNOSTIC_POSITIONS
-                    // Set start/end positions for discarded object.
+                // Set start/end positions for discarded object.
-                    handle_diagnostic_positions_for_json_value(*ref_stack.back());
+                handle_diagnostic_positions_for_json_value(*ref_stack.back());
 #endif
-                }
             }
             else
             {
@@ -633,10 +617,6 @@ class json_sax_dom_callback_parser
 #endif
 
                 ref_stack.back()->set_parents();
-                // this object is finally, definitively kept; drop any
-                // pending duplicate-key stash entry for its slot since it
-                // can no longer be restored
-                resolve_duplicate_key_stash(ref_stack.back(), false);
             }
         }
 
@@ -679,7 +659,7 @@ class json_sax_dom_callback_parser
             // check array limit
             if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
             {
-                return parse_error(0, "", out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
+                JSON_THROW(out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
             }
         }
 
@@ -706,25 +686,16 @@ class json_sax_dom_callback_parser
 #endif
 
                 ref_stack.back()->set_parents();
-                // this array is finally, definitively kept; drop any
-                // pending duplicate-key stash entry for its slot since it
-                // can no longer be restored
-                resolve_duplicate_key_stash(ref_stack.back(), false);
             }
             else
             {
-                // discard array, unless this slot holds a duplicate key's
+                // discard array
-                // previous value pending restoration, in which case that
+                *ref_stack.back() = discarded;
-                // value is restored instead of being discarded
-                if (!resolve_duplicate_key_stash(ref_stack.back(), true))
-                {
-                    *ref_stack.back() = discarded;
 
 #if JSON_DIAGNOSTIC_POSITIONS
-                    // Set start/end positions for discarded array.
+                // Set start/end positions for discarded array.
-                    handle_diagnostic_positions_for_json_value(*ref_stack.back());
+                handle_diagnostic_positions_for_json_value(*ref_stack.back());
 #endif
-                }
             }
         }
 
@@ -838,48 +809,14 @@ class json_sax_dom_callback_parser
     }
 #endif
 
-    /// if there is a pending duplicate-key stash entry for this exact slot,
+    /// remove the discarded value the callback rejected from its parent
-    /// remove it from the stash; if restore_value is true, the stashed
+    static void remove_discarded_value(BasicJsonType& parent)
-    /// previous value is moved back into the slot first (use this when the
-    /// new value at that slot was rejected); otherwise the stash entry is
-    /// simply dropped (use this when the new value was accepted, so it
-    /// correctly supersedes the old one and no restore should ever happen
-    /// for this slot again)
-    /// @return whether a matching stash entry was found (and processed)
-    bool resolve_duplicate_key_stash(BasicJsonType* slot, bool restore_value)
-    {
-        const auto it = std::find_if(duplicate_key_stash.begin(), duplicate_key_stash.end(),
-                                     [slot](const std::pair<BasicJsonType*, BasicJsonType>& entry)
-        {
-            return entry.first == slot;
-        });
-
-        if (it == duplicate_key_stash.end())
-        {
-            return false;
-        }
-
-        if (restore_value)
-        {
-            *slot = std::move(it->second);
-        }
-        duplicate_key_stash.erase(it);
-        return true;
-    }
-
-    /// remove the discarded value the callback rejected from its parent,
-    /// unless it is a duplicate key's slot with a stashed previous value,
-    /// in which case that previous value is restored instead
-    void remove_discarded_value(BasicJsonType& parent)
     {
         for (auto it = parent.begin(); it != parent.end(); ++it)
         {
             if (it->is_discarded())
             {
-                if (!resolve_duplicate_key_stash(&(*it), true))
+                parent.erase(it);
-                {
-                    parent.erase(it);
-                }
                 break;
             }
         }
@@ -977,16 +914,6 @@ class json_sax_dom_callback_parser
 
         JSON_ASSERT(object_element);
         *object_element = std::move(value);
-        if (!skip_callback)
-        {
-            // this scalar value finally, definitively replaces whatever was
-            // at this slot; drop any pending duplicate-key stash entry for
-            // it since it can no longer be restored (a container value at
-            // this slot is resolved later, in end_object()/end_array(),
-            // since skip_callback is true for the placeholder handling that
-            // happens here for those)
-            resolve_duplicate_key_stash(object_element, false);
-        }
         return {true, object_element};
     }
 
@@ -1000,12 +927,6 @@ class json_sax_dom_callback_parser
     std::vector<bool> key_keep_stack {}; // NOLINT(readability-redundant-member-init)
     /// helper to hold the reference for the next object element
     BasicJsonType* object_element = nullptr;
-    /// stash of (slot pointer, previous value) for object members that
-    /// already existed when key() was called again for the same key
-    /// (duplicate keys); used to restore the previous value if the new
-    /// value is later rejected by the callback, instead of erasing the
-    /// member entirely
-    std::vector<std::pair<BasicJsonType*, BasicJsonType>> duplicate_key_stash {};
     /// whether a syntax error occurred
     bool errored = false;
     /// callback function

include/nlohmann/json.hpp

@@ -3573,7 +3573,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         {
             using std::swap;
             swap(*(m_data.m_value.array), other);
-            set_parents();
         }
         else
         {
@@ -3590,7 +3589,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         {
             using std::swap;
             swap(*(m_data.m_value.object), other);
-            set_parents();
         }
         else
         {
@@ -4941,6 +4939,12 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                 // note erase performs range check
                 parent.erase(json_pointer::template array_index<basic_json_t>(last_path));
             }
+            else
+            {
+                // the parent of a "remove" target must be an object or array
+                // (see #5396)
+                JSON_THROW(out_of_range::create(413, detail::concat("cannot remove value: the JSON Patch 'remove' target's parent is of type ", parent.type_name(), ", but must be an object or array"), &parent));
+            }
         };
 
         // type check: top level value must be an array
@@ -5159,139 +5163,34 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
             case value_t::object:
             {
-                // first pass: record, for every source key, whether it is
+                // first pass: traverse this object's elements
-                // 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)
                 {
+                    // escape the key name to be used in a JSON patch
+                    const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+
                     if (target.find(it.key()) != target.end())
                     {
-                        common_keys_source_order.push_back(it.key());
+                        // recursive call to compare object values at key it
-                    }
+                        auto temp_diff = diff(it.value(), target[it.key()], path_key);
-                }
+                        result.insert(result.end(), temp_diff.begin(), temp_diff.end());
-
-                // 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): for an object_t whose iteration order is
-                // a pure function of the key set (e.g. the default std::map,
-                // which always iterates in sorted key order), the order
-                // check further below is always true and this whole
-                // mechanism is effectively a no-op; it only matters for a
-                // reorderable object_t such as the one backing `ordered_json`.
-                // 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
                     {
-                        common_keys_target_order.push_back(it.key());
+                        // found a key that is not in o -> remove it
-                        if (seen_new_key)
-                        {
-                            new_keys_form_suffix = false;
-                        }
-                    }
-                }
-
-                if (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_source_order.cend() && it.key() == *common_it)
-                        {
-                            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
-                            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 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
+                // second pass: traverse other object's elements
-                    // above) or brand new, in target's iteration order, so
+                for (auto it = target.cbegin(); it != target.cend(); ++it)
-                    // that the final order after applying the patch matches
+                {
-                    // target exactly
+                    if (source.find(it.key()) == source.end())
-                    for (auto it = target.cbegin(); it != target.cend(); ++it)
                     {
+                        // found a key that is not in this -> add it
                         const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
                         result.push_back(
                         {

single_include/nlohmann/json.hpp

@@ -7768,11 +7768,10 @@ NLOHMANN_JSON_NAMESPACE_END
 
 
 
-#include <algorithm> // find_if
 #include <cstddef>
 #include <string> // string
 #include <type_traits> // enable_if_t
-#include <utility> // move, pair
+#include <utility> // move
 #include <vector> // vector
 
 // #include <nlohmann/detail/exceptions.hpp>
@@ -9778,7 +9777,7 @@ class json_sax_dom_parser
 
         if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
         {
-            return parse_error(0, "", out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
+            JSON_THROW(out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
         }
 
         return true;
@@ -9827,7 +9826,7 @@ class json_sax_dom_parser
 
         if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
         {
-            return parse_error(0, "", out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
+            JSON_THROW(out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
         }
 
         return true;
@@ -10097,7 +10096,7 @@ class json_sax_dom_callback_parser
             // check object limit
             if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
             {
-                return parse_error(0, "", out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
+                JSON_THROW(out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
             }
         }
         return true;
@@ -10114,17 +10113,7 @@ class json_sax_dom_callback_parser
         // add discarded value at the given key and store the reference for later
         if (keep && ref_stack.back())
         {
-            auto& obj = *ref_stack.back()->m_data.m_value.object;
+            object_element = &(ref_stack.back()->m_data.m_value.object->operator[](val) = discarded);
-            const auto it = obj.find(val);
-            if (it != obj.end())
-            {
-                // this is a duplicate key (legal in JSON); remember its
-                // current value so it can be restored later if the new
-                // value is rejected by the callback, instead of being
-                // erased together with the discarded placeholder
-                duplicate_key_stash.emplace_back(&(it->second), it->second);
-            }
-            object_element = &(obj[val] = discarded);
         }
 
         return true;
@@ -10136,18 +10125,13 @@ class json_sax_dom_callback_parser
         {
             if (!callback(static_cast<int>(ref_stack.size()) - 1, parse_event_t::object_end, *ref_stack.back()))
             {
-                // discard object, unless this slot holds a duplicate key's
+                // discard object
-                // previous value pending restoration, in which case that
+                *ref_stack.back() = discarded;
-                // value is restored instead of being discarded
-                if (!resolve_duplicate_key_stash(ref_stack.back(), true))
-                {
-                    *ref_stack.back() = discarded;
 
 #if JSON_DIAGNOSTIC_POSITIONS
-                    // Set start/end positions for discarded object.
+                // Set start/end positions for discarded object.
-                    handle_diagnostic_positions_for_json_value(*ref_stack.back());
+                handle_diagnostic_positions_for_json_value(*ref_stack.back());
 #endif
-                }
             }
             else
             {
@@ -10161,10 +10145,6 @@ class json_sax_dom_callback_parser
 #endif
 
                 ref_stack.back()->set_parents();
-                // this object is finally, definitively kept; drop any
-                // pending duplicate-key stash entry for its slot since it
-                // can no longer be restored
-                resolve_duplicate_key_stash(ref_stack.back(), false);
             }
         }
 
@@ -10207,7 +10187,7 @@ class json_sax_dom_callback_parser
             // check array limit
             if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
             {
-                return parse_error(0, "", out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
+                JSON_THROW(out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
             }
         }
 
@@ -10234,25 +10214,16 @@ class json_sax_dom_callback_parser
 #endif
 
                 ref_stack.back()->set_parents();
-                // this array is finally, definitively kept; drop any
-                // pending duplicate-key stash entry for its slot since it
-                // can no longer be restored
-                resolve_duplicate_key_stash(ref_stack.back(), false);
             }
             else
             {
-                // discard array, unless this slot holds a duplicate key's
+                // discard array
-                // previous value pending restoration, in which case that
+                *ref_stack.back() = discarded;
-                // value is restored instead of being discarded
-                if (!resolve_duplicate_key_stash(ref_stack.back(), true))
-                {
-                    *ref_stack.back() = discarded;
 
 #if JSON_DIAGNOSTIC_POSITIONS
-                    // Set start/end positions for discarded array.
+                // Set start/end positions for discarded array.
-                    handle_diagnostic_positions_for_json_value(*ref_stack.back());
+                handle_diagnostic_positions_for_json_value(*ref_stack.back());
 #endif
-                }
             }
         }
 
@@ -10366,48 +10337,14 @@ class json_sax_dom_callback_parser
     }
 #endif
 
-    /// if there is a pending duplicate-key stash entry for this exact slot,
+    /// remove the discarded value the callback rejected from its parent
-    /// remove it from the stash; if restore_value is true, the stashed
+    static void remove_discarded_value(BasicJsonType& parent)
-    /// previous value is moved back into the slot first (use this when the
-    /// new value at that slot was rejected); otherwise the stash entry is
-    /// simply dropped (use this when the new value was accepted, so it
-    /// correctly supersedes the old one and no restore should ever happen
-    /// for this slot again)
-    /// @return whether a matching stash entry was found (and processed)
-    bool resolve_duplicate_key_stash(BasicJsonType* slot, bool restore_value)
-    {
-        const auto it = std::find_if(duplicate_key_stash.begin(), duplicate_key_stash.end(),
-                                     [slot](const std::pair<BasicJsonType*, BasicJsonType>& entry)
-        {
-            return entry.first == slot;
-        });
-
-        if (it == duplicate_key_stash.end())
-        {
-            return false;
-        }
-
-        if (restore_value)
-        {
-            *slot = std::move(it->second);
-        }
-        duplicate_key_stash.erase(it);
-        return true;
-    }
-
-    /// remove the discarded value the callback rejected from its parent,
-    /// unless it is a duplicate key's slot with a stashed previous value,
-    /// in which case that previous value is restored instead
-    void remove_discarded_value(BasicJsonType& parent)
     {
         for (auto it = parent.begin(); it != parent.end(); ++it)
         {
             if (it->is_discarded())
             {
-                if (!resolve_duplicate_key_stash(&(*it), true))
+                parent.erase(it);
-                {
-                    parent.erase(it);
-                }
                 break;
             }
         }
@@ -10505,16 +10442,6 @@ class json_sax_dom_callback_parser
 
         JSON_ASSERT(object_element);
         *object_element = std::move(value);
-        if (!skip_callback)
-        {
-            // this scalar value finally, definitively replaces whatever was
-            // at this slot; drop any pending duplicate-key stash entry for
-            // it since it can no longer be restored (a container value at
-            // this slot is resolved later, in end_object()/end_array(),
-            // since skip_callback is true for the placeholder handling that
-            // happens here for those)
-            resolve_duplicate_key_stash(object_element, false);
-        }
         return {true, object_element};
     }
 
@@ -10528,12 +10455,6 @@ class json_sax_dom_callback_parser
     std::vector<bool> key_keep_stack {}; // NOLINT(readability-redundant-member-init)
     /// helper to hold the reference for the next object element
     BasicJsonType* object_element = nullptr;
-    /// stash of (slot pointer, previous value) for object members that
-    /// already existed when key() was called again for the same key
-    /// (duplicate keys); used to restore the previous value if the new
-    /// value is later rejected by the callback, instead of erasing the
-    /// member entirely
-    std::vector<std::pair<BasicJsonType*, BasicJsonType>> duplicate_key_stash {};
     /// whether a syntax error occurred
     bool errored = false;
     /// callback function
@@ -25080,7 +25001,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         {
             using std::swap;
             swap(*(m_data.m_value.array), other);
-            set_parents();
         }
         else
         {
@@ -25097,7 +25017,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         {
             using std::swap;
             swap(*(m_data.m_value.object), other);
-            set_parents();
         }
         else
         {
@@ -26448,6 +26367,12 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                 // note erase performs range check
                 parent.erase(json_pointer::template array_index<basic_json_t>(last_path));
             }
+            else
+            {
+                // the parent of a "remove" target must be an object or array
+                // (see #5396)
+                JSON_THROW(out_of_range::create(413, detail::concat("cannot remove value: the JSON Patch 'remove' target's parent is of type ", parent.type_name(), ", but must be an object or array"), &parent));
+            }
         };
 
         // type check: top level value must be an array
@@ -26666,139 +26591,34 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
             case value_t::object:
             {
-                // first pass: record, for every source key, whether it is
+                // first pass: traverse this object's elements
-                // 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)
                 {
+                    // escape the key name to be used in a JSON patch
+                    const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+
                     if (target.find(it.key()) != target.end())
                     {
-                        common_keys_source_order.push_back(it.key());
+                        // recursive call to compare object values at key it
-                    }
+                        auto temp_diff = diff(it.value(), target[it.key()], path_key);
-                }
+                        result.insert(result.end(), temp_diff.begin(), temp_diff.end());
-
-                // 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): for an object_t whose iteration order is
-                // a pure function of the key set (e.g. the default std::map,
-                // which always iterates in sorted key order), the order
-                // check further below is always true and this whole
-                // mechanism is effectively a no-op; it only matters for a
-                // reorderable object_t such as the one backing `ordered_json`.
-                // 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
                     {
-                        common_keys_target_order.push_back(it.key());
+                        // found a key that is not in o -> remove it
-                        if (seen_new_key)
-                        {
-                            new_keys_form_suffix = false;
-                        }
-                    }
-                }
-
-                if (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_source_order.cend() && it.key() == *common_it)
-                        {
-                            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
-                            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 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
+                // second pass: traverse other object's elements
-                    // above) or brand new, in target's iteration order, so
+                for (auto it = target.cbegin(); it != target.cend(); ++it)
-                    // that the final order after applying the patch matches
+                {
-                    // target exactly
+                    if (source.find(it.key()) == source.end())
-                    for (auto it = target.cbegin(); it != target.cend(); ++it)
                     {
+                        // found a key that is not in this -> add it
                         const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
                         result.push_back(
                         {

tests/src/unit-diagnostics.cpp

@@ -273,36 +273,5 @@ TEST_CASE("Regression tests for extended diagnostics")
         CHECK(j1["numbers"]["two"] == 2);
         CHECK(j1["string"] == "t");
     }
-
-    SECTION("Regression test - swap(array_t&)/swap(object_t&) must update JSON_DIAGNOSTICS parent pointers")
-    {
-        // swap(array_t&)
-        {
-            json j = json::array();
-            json::array_t arr = {json::array({1})};
-            j.swap(arr);
-
-            // parent pointers of the moved-in elements must point into j, not
-            // into the now-defunct free-standing array_t
-            CHECK_THROWS_WITH_AS(j[0][0].get<std::string>(), "[json.exception.type_error.302] (/0/0) type must be string, but is number", json::type_error);
-
-            // must not trigger assert_invariant() in a debug/assert-enabled build
-            json const k = j;
-            CHECK(k == j);
-        }
-
-        // swap(object_t&)
-        {
-            json o = json::object();
-            json::object_t obj = {{"a", json::array({1})}};
-            o.swap(obj);
-
-            CHECK_THROWS_WITH_AS(o["a"][0].get<std::string>(), "[json.exception.type_error.302] (/a/0) type must be string, but is number", json::type_error);
-
-            // must not trigger assert_invariant() in a debug/assert-enabled build
-            json const p = o;
-            CHECK(p == o);
-        }
-    }
 }
 

tests/src/unit-json_patch.cpp

@@ -1389,6 +1389,61 @@ TEST_CASE("JSON patch - add to a primitive parent (regression #4292)")
     }
 }
 
+TEST_CASE("JSON patch - remove with primitive or null parent (regression #5396)")
+{
+    // Regression test for https://github.com/nlohmann/json/issues/5396
+    //
+    // RFC 6902 (§4.2) requires the target location of a "remove" operation
+    // to exist. When the target's parent resolves to a primitive value or
+    // null, the operation must fail. Previously operation_remove silently
+    // did nothing in this case (neither the "is_object" nor the "is_array"
+    // branch matched, and there was no final "else"), so the patch appeared
+    // to succeed without changing the document. It now throws
+    // out_of_range.413.
+
+    SECTION("parent is a primitive (number)")
+    {
+        json const doc = {{"a", 1}};
+        json const patch = {{{"op", "remove"}, {"path", "/a/b"}}};
+#if JSON_DIAGNOSTICS
+        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] (/a) cannot remove value: the JSON Patch 'remove' target's parent is of type number, but must be an object or array", json::out_of_range&);
+#else
+        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] cannot remove value: the JSON Patch 'remove' target's parent is of type number, but must be an object or array", json::out_of_range&);
+#endif
+    }
+
+    SECTION("parent is a primitive (string)")
+    {
+        json const doc = {{"foo", {{"bar", "a string"}}}};
+        json const patch = {{{"op", "remove"}, {"path", "/foo/bar/baz"}}};
+#if JSON_DIAGNOSTICS
+        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] (/foo/bar) cannot remove value: the JSON Patch 'remove' target's parent is of type string, but must be an object or array", json::out_of_range&);
+#else
+        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] cannot remove value: the JSON Patch 'remove' target's parent is of type string, but must be an object or array", json::out_of_range&);
+#endif
+    }
+
+    SECTION("top-level document is null")
+    {
+        json const doc = nullptr;
+        json const patch = {{{"op", "remove"}, {"path", "/a"}}};
+        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] cannot remove value: the JSON Patch 'remove' target's parent is of type null, but must be an object or array", json::out_of_range&);
+    }
+
+    SECTION("legitimate removes still work")
+    {
+        // object member
+        json const doc1 = {{"a", 1}, {"b", 2}};
+        json const patch1 = {{{"op", "remove"}, {"path", "/a"}}};
+        CHECK(doc1.patch(patch1) == json({{"b", 2}}));
+
+        // array element
+        json const doc2 = R"([1, 2, 3])"_json;
+        json const patch2 = {{{"op", "remove"}, {"path", "/1"}}};
+        CHECK(doc2.patch(patch2) == R"([1, 3])"_json);
+    }
+}
+
 TEST_CASE("JSON patch - diff emits array removals in descending index order")
 {
     SECTION("array shrunk to empty")

tests/src/unit-ordered_json.cpp

@@ -81,84 +81,3 @@ TEST_CASE("regression test for issue #3732 - iteration_proxy_value<iter_impl<ord
     };
     static_cast<void>(fn);
 }
-
-TEST_CASE("regression test - diff() must account for ordered_json member order")
-{
-    SECTION("pure reorder, no value changes")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}};
-        ordered_json b = {{"b", 2}, {"a", 1}};
-        CHECK(a != b); // order-sensitive equality
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("new key must land at the front")
-    {
-        ordered_json c = {{"b", 2}};
-        ordered_json e = {{"a", 1}, {"b", 2}};
-        CHECK(c.patch(ordered_json::diff(c, e)) == e);
-    }
-
-    SECTION("reorder plus a value change on one of the reordered keys")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}};
-        ordered_json b = {{"b", 20}, {"a", 1}};
-        CHECK(a != b);
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("reorder plus a deleted key")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}, {"c", 3}};
-        ordered_json b = {{"b", 2}, {"a", 1}};
-        CHECK(a != b);
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("reorder plus a nested value that itself needs a recursive diff")
-    {
-        ordered_json a = {{"a", {{"x", 1}, {"y", 2}}}, {"b", 2}};
-        ordered_json b = {{"b", 2}, {"a", {{"x", 1}, {"y", 99}}}};
-        CHECK(a != b);
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("three or more keys shuffled into a different order")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}};
-        ordered_json b = {{"d", 4}, {"b", 2}, {"a", 1}, {"c", 3}};
-        CHECK(a != b);
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("matching order still produces a minimal patch (fast path unaffected)")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}, {"c", 3}};
-        ordered_json b = {{"a", 1}, {"b", 20}, {"c", 3}};
-        auto p = ordered_json::diff(a, b);
-        // only the changed value should be touched, not a wholesale remove+add
-        CHECK(p.size() == 1);
-        CHECK(p[0]["op"] == "replace");
-        CHECK(p[0]["path"] == "/b");
-        CHECK(a.patch(p) == b);
-    }
-
-    SECTION("plain json (std::map-backed) is unaffected by same-key-different-insertion-order")
-    {
-        json a;
-        a["b"] = 2;
-        a["a"] = 1;
-
-        json b;
-        b["a"] = 1;
-        b["b"] = 2;
-
-        // std::map iteration is always sorted by key, so a == b regardless of
-        // insertion order, and diff() must still produce the same minimal
-        // (empty) result as before this fix
-        CHECK(a == b);
-        auto p = json::diff(a, b);
-        CHECK(p.empty());
-        CHECK(a.patch(p) == b);
-    }
-}

tests/src/unit-regression2.cpp

@@ -1566,106 +1566,4 @@ TEST_CASE("issue #5402 - update(merge_objects=true) overwrites a primitive with
     CHECK(mixed == json({{"keep", {{"a", 1}, {"b", 2}}}, {"replace", {{"x", 2}}}}));
 }
 
-TEST_CASE("regression test - parser callback must not lose a duplicate key's prior value")
-{
-    // a callback that rejects only the scalar value 2
-    const json::parser_callback_t drop_value_2 = [](int /*depth*/, json::parse_event_t ev, json & v) noexcept
-    {
-        return !(ev == json::parse_event_t::value && v == 2);
-    };
-
-    SECTION("duplicate key, second (scalar) value rejected - prior value is restored")
-    {
-        const json j = json::parse(R"({"a":1,"a":2})", drop_value_2);
-        CHECK(j.dump() == "{\"a\":1}");
-    }
-
-    SECTION("duplicate key, second value is an object rejected at object_end - prior value is restored")
-    {
-        const json j = json::parse(R"({"a":1,"a":{"x":2}})",
-                                   [](int depth, json::parse_event_t ev, json& /*parsed*/) noexcept
-        {
-            return !(ev == json::parse_event_t::object_end && depth == 1);
-        });
-        CHECK(j.dump() == "{\"a\":1}");
-    }
-
-    SECTION("duplicate key, second value is an array rejected at array_end - prior value is restored")
-    {
-        const json j = json::parse(R"({"a":1,"a":[9,9]})",
-                                   [](int depth, json::parse_event_t ev, json& /*parsed*/) noexcept
-        {
-            return !(ev == json::parse_event_t::array_end && depth == 1);
-        });
-        CHECK(j.dump() == "{\"a\":1}");
-    }
-
-    SECTION("duplicate key, second value accepted (scalar) - last value wins")
-    {
-        const json j = json::parse(R"({"a":1,"a":2})", [](int, json::parse_event_t, json&) noexcept
-        {
-            return true;
-        });
-        CHECK(j.dump() == "{\"a\":2}");
-    }
-
-    SECTION("duplicate key, second value accepted (object) - last value wins")
-    {
-        const json j = json::parse(R"({"a":1,"a":{"x":2}})", [](int, json::parse_event_t, json&) noexcept
-        {
-            return true;
-        });
-        CHECK(j.dump() == "{\"a\":{\"x\":2}}");
-    }
-
-    SECTION("brand new (non-duplicate) key, value rejected - member is fully absent")
-    {
-        const json j = json::parse(R"({"a":1,"b":2})", drop_value_2);
-        CHECK(j.dump() == "{\"a\":1}");
-    }
-
-    SECTION("duplicate key nested two levels deep")
-    {
-        const json j = json::parse(R"({"outer":{"a":1,"a":2}})", drop_value_2);
-        CHECK(j.dump() == "{\"outer\":{\"a\":1}}");
-    }
-
-    SECTION("three occurrences of the same key - middle rejected, last accepted")
-    {
-        const json j = json::parse(R"({"k":1,"k":2,"k":3})", drop_value_2);
-        CHECK(j.dump() == "{\"k\":3}");
-    }
-}
-
-TEST_CASE("regression test - excessive binary container size honors allow_exceptions=false")
-{
-    // CBOR array with declared length 2^63
-    const std::vector<std::uint8_t> cbor = {0x9b, 0x80, 0, 0, 0, 0, 0, 0, 0};
-    // CBOR map with declared length 2^63
-    const std::vector<std::uint8_t> cbor_m = {0xbb, 0x80, 0, 0, 0, 0, 0, 0, 0};
-    // UBJSON array with declared length 2^63-1
-    const std::vector<std::uint8_t> ubj = {'[', '#', 'L', 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
-    // BJData array with declared length 2^63-1 (little endian)
-    const std::vector<std::uint8_t> bjd = {'[', '#', 'L', 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f};
-
-    // allow_exceptions=false must report failure instead of throwing/aborting
-    CHECK(json::from_cbor(cbor, true, false).is_discarded());
-    CHECK(json::from_cbor(cbor_m, true, false).is_discarded());
-    CHECK(json::from_ubjson(ubj, true, false).is_discarded());
-    CHECK(json::from_bjdata(bjd, true, false).is_discarded());
-
-    // allow_exceptions=true (the default) must still throw exactly as before.
-    // The exact message text is not checked here: on platforms where
-    // std::size_t is 32-bit, the CBOR reader's own length-narrowing check
-    // (get_cbor_container_size(), unrelated to this fix) intercepts a
-    // declared length of 2^63 before it ever reaches the check this test
-    // targets, with different (but equally valid, and already correct)
-    // wording -- see unit-cbor.cpp for coverage of that message.
-    json _;
-    CHECK_THROWS_AS(_ = json::from_cbor(cbor), json::out_of_range);
-
-    // regression guard: a genuinely truncated CBOR input must remain discarded
-    CHECK(json::from_cbor(std::vector<std::uint8_t> {0x9b, 0, 0, 0, 0, 0, 0, 0, 0x02}, true, false).is_discarded());
-}
-
 DOCTEST_CLANG_SUPPRESS_WARNING_POP