Take diff()'s fast path unless the object type reorders members

For every object type except an insertion-ordered one like ordered_map,
diff() no longer produced a member-by-member patch when target had a key
that sorts before a key the two objects share: it fell through to the
slow path, which removes every member of source and re-adds every member
of target, instead of just adding the new key.

#5465 added an order check to require the fast path to also reproduce
target's member order, needed because ordered_map's patch()-driven "add"
appends a new member at the end. The check compared the common keys'
order between source and target and also required that every added key
come after every common key in target's order ("new_keys_form_suffix").
The comment above it argued this check is always true for std::map, and
that reasoning is correct for the order of the common keys themselves,
but not for new_keys_form_suffix: a std::map iterates in sorted key
order, so a new key that sorts before an existing common key is
enumerated between common keys, making new_keys_form_suffix false even
though std::map's own key order does not need reordering at all - it
places every member itself, regardless of insertion history, so a
member-by-member diff already reproduces target's iteration order.

Only require the order check for an object type that keeps insertion
order, using the same detail::is_ordered_map trait the library already
uses to recognize such an object type in set_parent(). Every other
object type - std::map in key order, a hash map in an order its
operator== ignores - always takes the fast path.

Added a regression test to unit-json_patch.cpp: the issue's example now
yields a single "add" op for json, while ordered_json still takes the
slow path to reproduce target's member order.

Fixes #5639.

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

docs/mkdocs/docs/api/basic_json/parser_callback_t.md

@@ -100,6 +100,3 @@ the latter case, it is skipped completely, or replaced by `null` if it is the to
 - Added in version 1.0.0.
 - Fixed in version 3.13.0 to also remove discarded values from a parent object; before, discarding an array or a value
   stored under an object key left a discarded member behind, which made the parse result serialize to invalid JSON.
-- Fixed in version 3.13.0 so that discarding an array or object at its start event also hides its content from the
-  callback, as documented above; before, the callback was still called for the content, and the key of every member of
-  a discarded object was kept in memory until the parse ended.

include/nlohmann/detail/input/json_sax.hpp

@@ -582,8 +582,8 @@ class json_sax_dom_callback_parser
 
     bool start_object(std::size_t len)
     {
-        // check callback for object start; not called inside a discarded container
-        const bool keep = keep_stack.back() && callback(static_cast<int>(ref_stack.size()), parse_event_t::object_start, discarded);
+        // check callback for object start
+        const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::object_start, discarded);
         keep_stack.push_back(keep);
 
         // the key this object will be stored under, read before handle_value()
@@ -619,18 +619,6 @@ class json_sax_dom_callback_parser
 
     bool key(string_t& val)
     {
-        if (!keep_stack.back() || !ref_stack.back())
-        {
-            // the object is not stored: the value of this key is dropped in
-            // handle_value() without touching the key stacks
-            if (keep_stack.back())
-            {
-                BasicJsonType k = BasicJsonType(val);
-                static_cast<void>(callback(static_cast<int>(ref_stack.size()), parse_event_t::key, k));
-            }
-            return true;
-        }
-
         BasicJsonType k = BasicJsonType(val);
 
         // check callback for the key
@@ -716,7 +704,7 @@ class json_sax_dom_callback_parser
 
     bool start_array(std::size_t len)
     {
-        const bool keep = keep_stack.back() && callback(static_cast<int>(ref_stack.size()), parse_event_t::array_start, discarded);
+        const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::array_start, discarded);
         keep_stack.push_back(keep);
 
         // see start_object()

include/nlohmann/json.hpp

@@ -6187,7 +6187,14 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                     }
                 }
 
-                if (common_keys_source_order == common_keys_target_order && new_keys_form_suffix)
+                // 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

single_include/nlohmann/json.hpp

@@ -11996,8 +11996,8 @@ class json_sax_dom_callback_parser
 
     bool start_object(std::size_t len)
     {
-        // check callback for object start; not called inside a discarded container
-        const bool keep = keep_stack.back() && callback(static_cast<int>(ref_stack.size()), parse_event_t::object_start, discarded);
+        // check callback for object start
+        const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::object_start, discarded);
         keep_stack.push_back(keep);
 
         // the key this object will be stored under, read before handle_value()
@@ -12033,18 +12033,6 @@ class json_sax_dom_callback_parser
 
     bool key(string_t& val)
     {
-        if (!keep_stack.back() || !ref_stack.back())
-        {
-            // the object is not stored: the value of this key is dropped in
-            // handle_value() without touching the key stacks
-            if (keep_stack.back())
-            {
-                BasicJsonType k = BasicJsonType(val);
-                static_cast<void>(callback(static_cast<int>(ref_stack.size()), parse_event_t::key, k));
-            }
-            return true;
-        }
-
         BasicJsonType k = BasicJsonType(val);
 
         // check callback for the key
@@ -12130,7 +12118,7 @@ class json_sax_dom_callback_parser
 
     bool start_array(std::size_t len)
     {
-        const bool keep = keep_stack.back() && callback(static_cast<int>(ref_stack.size()), parse_event_t::array_start, discarded);
+        const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::array_start, discarded);
         keep_stack.push_back(keep);
 
         // see start_object()
@@ -32280,7 +32268,14 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                     }
                 }
 
-                if (common_keys_source_order == common_keys_target_order && new_keys_form_suffix)
+                // 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

tests/src/unit-class_parser.cpp

@@ -1966,102 +1966,6 @@ TEST_CASE("parser class")
             }
         }
 
-        SECTION("no callback for the content of a discarded container (#5643)")
-        {
-            // discarding a container at its start event must also hide
-            // everything inside it from the callback: none of the nested
-            // keys, values, or nested containers' own start/end events may
-            // be reported
-            std::vector<std::string> log;
-            bool first = true;
-            const json j = json::parse(R"({"skip": {"k1": 1, "k2": [2, {"k3": 3}]}, "keep": 1})",
-                                       [&](int depth, json::parse_event_t event, json & parsed)
-            {
-                static const char* const names[] = {"object_start", "object_end", "array_start", "array_end", "key", "value"};
-                log.push_back(std::to_string(depth) + " " + names[static_cast<int>(event)] + " " + parsed.dump());
-
-                if (depth == 1 && event == json::parse_event_t::object_start && first)
-                {
-                    // discard "skip" right at its object_start event
-                    first = false;
-                    return false;
-                }
-                return true;
-            });
-
-            CHECK(log == std::vector<std::string>
-            {
-                "0 object_start <discarded>",
-                "1 key \"skip\"",
-                "1 object_start <discarded>",
-                "1 key \"keep\"",
-                "1 value 1",
-                "0 object_end {\"keep\":1}"
-            });
-            CHECK(j == json({{"keep", 1}}));
-        }
-
-        SECTION("callback still called inside a container whose key was rejected (#5643)")
-        {
-            // rejecting a key does not discard its value's container at the
-            // container's own start event, so the callback is still called
-            // for that container's content; only storing the container
-            // under the rejected key is skipped
-            // (documented for parser_callback_t: "the callback is still
-            // called for the associated value, but its return value has no
-            // further effect")
-            const auto record = [](std::vector<std::string>& log, int depth, json::parse_event_t event, const json & parsed)
-            {
-                static const char* const names[] = {"object_start", "object_end", "array_start", "array_end", "key", "value"};
-                log.push_back(std::to_string(depth) + " " + names[static_cast<int>(event)] + " " + parsed.dump());
-            };
-
-            std::vector<std::string> log_object;
-            const json j_object = json::parse(R"({"skip": {"k1": 1}, "keep": 2})",
-                                              [&](int depth, json::parse_event_t event, json & parsed)
-            {
-                record(log_object, depth, event, parsed);
-                return !(event == json::parse_event_t::key && parsed == json("skip"));
-            });
-
-            CHECK(log_object == std::vector<std::string>
-            {
-                "0 object_start <discarded>",
-                "1 key \"skip\"",
-                "1 object_start <discarded>",
-                "2 key \"k1\"",
-                "2 value 1",
-                "1 key \"keep\"",
-                "1 value 2",
-                "0 object_end {\"keep\":2}"
-            });
-            CHECK(j_object == json({{"keep", 2}}));
-
-            // same for a rejected key whose value is an array rather than an object
-            std::vector<std::string> log_array;
-            const json j_array = json::parse(R"({"skip": [1, {"k1": 2}], "keep": 2})",
-                                             [&](int depth, json::parse_event_t event, json & parsed)
-            {
-                record(log_array, depth, event, parsed);
-                return !(event == json::parse_event_t::key && parsed == json("skip"));
-            });
-
-            CHECK(log_array == std::vector<std::string>
-            {
-                "0 object_start <discarded>",
-                "1 key \"skip\"",
-                "1 array_start <discarded>",
-                "2 value 1",
-                "2 object_start <discarded>",
-                "3 key \"k1\"",
-                "3 value 2",
-                "1 key \"keep\"",
-                "1 value 2",
-                "0 object_end {\"keep\":2}"
-            });
-            CHECK(j_array == json({{"keep", 2}}));
-        }
-
         SECTION("special cases")
         {
             // the following test cases cover the situation in which an empty

tests/src/unit-json_patch.cpp

@@ -1752,6 +1752,58 @@ TEST_CASE("JSON patch - diff emits array removals in descending index order")
     }
 }
 
+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
+    // member-by-member diff is only used when it would also reproduce
+    // target's member *order* -- needed for ordered_json, whose object_t
+    // keeps insertion order and whose patch() "add" op appends a new
+    // member at the end. For json's default object_t (std::map, which
+    // orders members by key regardless of insertion history), that check
+    // could still fail: a new key that sorts before an existing common key
+    // makes target's iteration interleave the new key between common keys,
+    // even though nothing else about the object changed. That sent the
+    // whole object through the slow (remove-every-member,
+    // re-add-every-member) path instead of the minimal one.
+    SECTION("json: added key sorts before an existing common key")
+    {
+        const json source = {{"a", 1}, {"c", {{"x", 1}, {"y", 2}}}};
+        const json target = {{"a", 1}, {"b", 0}, {"c", {{"x", 1}, {"y", 2}}}};
+
+        const json patch = json::diff(source, target);
+
+        // only the new key is added; "a" and "c" are left alone instead of
+        // being removed and re-added
+        const json expected = R"([{"op": "add", "path": "/b", "value": 0}])"_json;
+        CHECK(patch == expected);
+        CHECK(source.patch(patch) == target);
+    }
+
+    SECTION("ordered_json: reordering behavior from #5465 is unchanged")
+    {
+        using nlohmann::ordered_json;
+
+        // same key/value shape as the json case above, but for ordered_json
+        // the *target*'s member order must be reproduced, so the slow path
+        // is still required here.
+        ordered_json source;
+        source["a"] = 1;
+        source["c"] = ordered_json{{"x", 1}, {"y", 2}};
+
+        ordered_json target;
+        target["a"] = 1;
+        target["b"] = 0;
+        target["c"] = ordered_json{{"x", 1}, {"y", 2}};
+
+        const ordered_json patch = ordered_json::diff(source, target);
+
+        // unlike the json case: every member is still removed and re-added
+        // so the result ends up in target's order (2 removes + 3 adds)
+        CHECK(patch.size() == 5);
+        CHECK(source.patch(patch) == target);
+    }
+}
+
 TEST_CASE("JSON patch - every operation on ordered_json")
 {
     using nlohmann::ordered_json;