Make diff() linear when an array shrinks (#5461)

Signed-off-by: avionicharshit-byte <harshitavionic@gmail.com>

include/nlohmann/detail/value_t.hpp

@@ -9,9 +9,12 @@
 #pragma once
 
 #include <array> // array
+#include <cmath> // isnan, ldexp, trunc
 #include <cstddef> // size_t
 #include <cstdint> // uint8_t
+#include <limits> // numeric_limits
 #include <string> // string
+#include <type_traits> // is_signed
 
 #include <nlohmann/detail/macro_scope.hpp>
 #if JSON_HAS_THREE_WAY_COMPARISON
@@ -114,5 +117,67 @@ inline bool operator<(const value_t lhs, const value_t rhs) noexcept
 }
 #endif
 
+
+/*!
+@brief compare an integer with a floating point number without precision loss
+
+Widening the integer to the floating point type loses precision beyond the
+float's mantissa, which makes equality intransitive: both 2^63-2 and 2^63-1
+round to 2^63, so each compares equal to that float while differing from each
+other. Ordering built on that is not a strict weak ordering, so sorting such
+values, or using them as keys in an ordered container, is undefined behavior.
+
+Returns a value to be compared against zero with the original operator, which
+reproduces the exact ordering. A NaN operand is returned as is, so comparing it
+against zero keeps NaN's semantics: false for the relational operators and
+unordered for `<=>`.
+*/
+template<typename IntegerType, typename FloatType>
+FloatType compare_integer_with_float(const IntegerType i, const FloatType f) noexcept
+{
+    const auto ordered = [](int c) noexcept
+    {
+        return static_cast<FloatType>(c);
+    };
+
+    if (std::isnan(f))
+    {
+        return f;
+    }
+
+    // values of IntegerType lie in [-bound, bound) when signed and in
+    // [0, bound) when unsigned; digits excludes the sign bit, so bound is a
+    // power of two that the float represents exactly
+    const FloatType bound = std::ldexp(static_cast<FloatType>(1), std::numeric_limits<IntegerType>::digits);
+    if (f >= bound)
+    {
+        return ordered(-1);
+    }
+    if (std::is_signed<IntegerType>::value ? (f < -bound) : (f < static_cast<FloatType>(0)))
+    {
+        return ordered(1);
+    }
+
+    // f is now within the integer's range, so truncating it is exact
+    const FloatType truncated = std::trunc(f);
+    const auto as_integer = static_cast<IntegerType>(truncated);
+    if (i != as_integer)
+    {
+        return ordered(i < as_integer ? -1 : 1);
+    }
+
+    // the integer parts agree, so any fractional part decides
+    const FloatType fraction = f - truncated;
+    if (fraction > static_cast<FloatType>(0))
+    {
+        return ordered(-1);
+    }
+    if (fraction < static_cast<FloatType>(0))
+    {
+        return ordered(1);
+    }
+    return ordered(0);
+}
+
 }  // namespace detail
 NLOHMANN_JSON_NAMESPACE_END

include/nlohmann/json.hpp

@@ -3703,19 +3703,19 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     }                                                                                                    \
     else if (lhs_type == value_t::number_integer && rhs_type == value_t::number_float)                   \
     {                                                                                                    \
-        return static_cast<number_float_t>(lhs.m_data.m_value.number_integer) op rhs.m_data.m_value.number_float;      \
+        return (detail::compare_integer_with_float(lhs.m_data.m_value.number_integer, rhs.m_data.m_value.number_float)) op (static_cast<number_float_t>(0)); \
     }                                                                                                    \
     else if (lhs_type == value_t::number_float && rhs_type == value_t::number_integer)                   \
     {                                                                                                    \
-        return lhs.m_data.m_value.number_float op static_cast<number_float_t>(rhs.m_data.m_value.number_integer);      \
+        return (static_cast<number_float_t>(0)) op (detail::compare_integer_with_float(rhs.m_data.m_value.number_integer, lhs.m_data.m_value.number_float)); \
     }                                                                                                    \
     else if (lhs_type == value_t::number_unsigned && rhs_type == value_t::number_float)                  \
     {                                                                                                    \
-        return static_cast<number_float_t>(lhs.m_data.m_value.number_unsigned) op rhs.m_data.m_value.number_float;     \
+        return (detail::compare_integer_with_float(lhs.m_data.m_value.number_unsigned, rhs.m_data.m_value.number_float)) op (static_cast<number_float_t>(0)); \
     }                                                                                                    \
     else if (lhs_type == value_t::number_float && rhs_type == value_t::number_unsigned)                  \
     {                                                                                                    \
-        return lhs.m_data.m_value.number_float op static_cast<number_float_t>(rhs.m_data.m_value.number_unsigned);     \
+        return (static_cast<number_float_t>(0)) op (detail::compare_integer_with_float(rhs.m_data.m_value.number_unsigned, lhs.m_data.m_value.number_float)); \
     }                                                                                                    \
     else if (lhs_type == value_t::number_unsigned && rhs_type == value_t::number_integer)                \
     {                                                                                                    \
@@ -5128,19 +5128,17 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                 // We now reached the end of at least one array
                 // in a second pass, traverse the remaining elements
 
-                // remove my remaining elements
-                const auto end_index = static_cast<difference_type>(result.size());
-                while (i < source.size())
+                // 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)
                 {
-                    // add operations in reverse order to avoid invalid
-                    // indices
-                    result.insert(result.begin() + end_index, object(
+                    result.push_back(object(
                     {
                         {"op", "remove"},
-                        {"path", detail::concat<string_t>(path, '/', detail::to_string<string_t>(i))}
+                        {"path", detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1))}
                     }));
-                    ++i;
                 }
+                i = source.size();
 
                 // add other remaining elements
                 while (i < target.size())

single_include/nlohmann/json.hpp

@@ -223,9 +223,12 @@
 
 
 #include <array> // array
+#include <cmath> // isnan, ldexp, trunc
 #include <cstddef> // size_t
 #include <cstdint> // uint8_t
+#include <limits> // numeric_limits
 #include <string> // string
+#include <type_traits> // is_signed
 
 // #include <nlohmann/detail/macro_scope.hpp>
 //     __ _____ _____ _____
@@ -3283,6 +3286,68 @@ inline bool operator<(const value_t lhs, const value_t rhs) noexcept
 }
 #endif
 
+
+/*!
+@brief compare an integer with a floating point number without precision loss
+
+Widening the integer to the floating point type loses precision beyond the
+float's mantissa, which makes equality intransitive: both 2^63-2 and 2^63-1
+round to 2^63, so each compares equal to that float while differing from each
+other. Ordering built on that is not a strict weak ordering, so sorting such
+values, or using them as keys in an ordered container, is undefined behavior.
+
+Returns a value to be compared against zero with the original operator, which
+reproduces the exact ordering. A NaN operand is returned as is, so comparing it
+against zero keeps NaN's semantics: false for the relational operators and
+unordered for `<=>`.
+*/
+template<typename IntegerType, typename FloatType>
+FloatType compare_integer_with_float(const IntegerType i, const FloatType f) noexcept
+{
+    const auto ordered = [](int c) noexcept
+    {
+        return static_cast<FloatType>(c);
+    };
+
+    if (std::isnan(f))
+    {
+        return f;
+    }
+
+    // values of IntegerType lie in [-bound, bound) when signed and in
+    // [0, bound) when unsigned; digits excludes the sign bit, so bound is a
+    // power of two that the float represents exactly
+    const FloatType bound = std::ldexp(static_cast<FloatType>(1), std::numeric_limits<IntegerType>::digits);
+    if (f >= bound)
+    {
+        return ordered(-1);
+    }
+    if (std::is_signed<IntegerType>::value ? (f < -bound) : (f < static_cast<FloatType>(0)))
+    {
+        return ordered(1);
+    }
+
+    // f is now within the integer's range, so truncating it is exact
+    const FloatType truncated = std::trunc(f);
+    const auto as_integer = static_cast<IntegerType>(truncated);
+    if (i != as_integer)
+    {
+        return ordered(i < as_integer ? -1 : 1);
+    }
+
+    // the integer parts agree, so any fractional part decides
+    const FloatType fraction = f - truncated;
+    if (fraction > static_cast<FloatType>(0))
+    {
+        return ordered(-1);
+    }
+    if (fraction < static_cast<FloatType>(0))
+    {
+        return ordered(1);
+    }
+    return ordered(0);
+}
+
 }  // namespace detail
 NLOHMANN_JSON_NAMESPACE_END
 
@@ -25057,19 +25122,19 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     }                                                                                                    \
     else if (lhs_type == value_t::number_integer && rhs_type == value_t::number_float)                   \
     {                                                                                                    \
-        return static_cast<number_float_t>(lhs.m_data.m_value.number_integer) op rhs.m_data.m_value.number_float;      \
+        return (detail::compare_integer_with_float(lhs.m_data.m_value.number_integer, rhs.m_data.m_value.number_float)) op (static_cast<number_float_t>(0)); \
     }                                                                                                    \
     else if (lhs_type == value_t::number_float && rhs_type == value_t::number_integer)                   \
     {                                                                                                    \
-        return lhs.m_data.m_value.number_float op static_cast<number_float_t>(rhs.m_data.m_value.number_integer);      \
+        return (static_cast<number_float_t>(0)) op (detail::compare_integer_with_float(rhs.m_data.m_value.number_integer, lhs.m_data.m_value.number_float)); \
     }                                                                                                    \
     else if (lhs_type == value_t::number_unsigned && rhs_type == value_t::number_float)                  \
     {                                                                                                    \
-        return static_cast<number_float_t>(lhs.m_data.m_value.number_unsigned) op rhs.m_data.m_value.number_float;     \
+        return (detail::compare_integer_with_float(lhs.m_data.m_value.number_unsigned, rhs.m_data.m_value.number_float)) op (static_cast<number_float_t>(0)); \
     }                                                                                                    \
     else if (lhs_type == value_t::number_float && rhs_type == value_t::number_unsigned)                  \
     {                                                                                                    \
-        return lhs.m_data.m_value.number_float op static_cast<number_float_t>(rhs.m_data.m_value.number_unsigned);     \
+        return (static_cast<number_float_t>(0)) op (detail::compare_integer_with_float(rhs.m_data.m_value.number_unsigned, lhs.m_data.m_value.number_float)); \
     }                                                                                                    \
     else if (lhs_type == value_t::number_unsigned && rhs_type == value_t::number_integer)                \
     {                                                                                                    \
@@ -26482,19 +26547,17 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                 // We now reached the end of at least one array
                 // in a second pass, traverse the remaining elements
 
-                // remove my remaining elements
-                const auto end_index = static_cast<difference_type>(result.size());
-                while (i < source.size())
+                // 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)
                 {
-                    // add operations in reverse order to avoid invalid
-                    // indices
-                    result.insert(result.begin() + end_index, object(
+                    result.push_back(object(
                     {
                         {"op", "remove"},
-                        {"path", detail::concat<string_t>(path, '/', detail::to_string<string_t>(i))}
+                        {"path", detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1))}
                     }));
-                    ++i;
                 }
+                i = source.size();
 
                 // add other remaining elements
                 while (i < target.size())

tests/src/unit-comparison.cpp

@@ -326,6 +326,57 @@ TEST_CASE("lexicographical comparison operators")
 #endif
         }
 
+        SECTION("integer/float mixed comparison is exact")
+        {
+            // Widening the integer to a double loses precision past the
+            // mantissa, so 2^63-2 and 2^63-1 both used to compare equal to the
+            // double 2^63 while differing from each other. That makes equality
+            // intransitive and the ordering not a strict weak ordering.
+            const json below_two_63 = static_cast<std::int64_t>(9223372036854775806LL);
+            const json max_int64 = (std::numeric_limits<std::int64_t>::max)();
+            const json two_63 = 9223372036854775808.0;
+
+            CHECK_FALSE(below_two_63 == two_63);
+            CHECK_FALSE(max_int64 == two_63);
+            CHECK(below_two_63 != max_int64);
+            CHECK(below_two_63 < max_int64);
+            CHECK(below_two_63 < two_63);
+            CHECK(max_int64 < two_63);
+            CHECK(two_63 > max_int64);
+            CHECK_FALSE(two_63 < max_int64);
+
+            // the same past the unsigned range
+            const json max_uint64 = (std::numeric_limits<std::uint64_t>::max)();
+            const json two_64 = 18446744073709551616.0;
+            CHECK_FALSE(max_uint64 == two_64);
+            CHECK(max_uint64 < two_64);
+            CHECK(two_64 > max_uint64);
+
+            // values a double represents exactly still compare equal
+            CHECK(json(1) == json(1.0));
+            CHECK(json(1u) == json(1.0));
+            CHECK(json(-3) == json(-3.0));
+            CHECK(json(1) < json(1.5));
+            CHECK(json(1.5) < json(2));
+            CHECK(json(2) > json(1.5));
+
+            // a NaN operand stays unordered against either integer kind
+            CHECK_FALSE(json(1) == json(nan));
+            CHECK_FALSE(json(1) < json(nan));
+            CHECK_FALSE(json(nan) < json(1));
+            CHECK_FALSE(json(1u) == json(nan));
+
+#if JSON_HAS_THREE_WAY_COMPARISON
+            // JSON_HAS_CPP_20 (do not remove; see note at top of file)
+            CHECK((max_int64 <=> two_63) == std::partial_ordering::less); // *NOPAD*
+            CHECK((two_63 <=> max_int64) == std::partial_ordering::greater); // *NOPAD*
+            CHECK((below_two_63 <=> max_int64) == std::partial_ordering::less); // *NOPAD*
+            CHECK((max_uint64 <=> two_64) == std::partial_ordering::less); // *NOPAD*
+            CHECK((json(1) <=> json(1.0)) == std::partial_ordering::equivalent); // *NOPAD*
+            CHECK((json(1) <=> json(nan)) == std::partial_ordering::unordered); // *NOPAD*
+#endif
+        }
+
         SECTION("compares unordered")
         {
             std::vector<std::vector<bool>> expected =

tests/src/unit-json_patch.cpp

@@ -1388,3 +1388,84 @@ TEST_CASE("JSON patch - add to a primitive parent (regression #4292)")
         CHECK_THROWS_AS(doc.patch(patch), json::out_of_range&);
     }
 }
+
+TEST_CASE("JSON patch - diff emits array removals in descending index order")
+{
+    SECTION("array shrunk to empty")
+    {
+        json const source = {0, 1, 2, 3, 4};
+        json const target = json::array();
+
+        json const patch = json::diff(source, target);
+
+        json const expected = R"(
+            [
+                {"op": "remove", "path": "/4"},
+                {"op": "remove", "path": "/3"},
+                {"op": "remove", "path": "/2"},
+                {"op": "remove", "path": "/1"},
+                {"op": "remove", "path": "/0"}
+            ]
+        )"_json;
+
+        CHECK(patch == expected);
+        CHECK(source.patch(patch) == target);
+    }
+
+    SECTION("array partially shrunk, after a replacement at a common index")
+    {
+        json const source = {0, 1, 2, 3, 4};
+        json const target = {0, 9};
+
+        json const patch = json::diff(source, target);
+
+        // the replacement comes first, then the removals, highest index first
+        json const expected = R"(
+            [
+                {"op": "replace", "path": "/1", "value": 9},
+                {"op": "remove", "path": "/4"},
+                {"op": "remove", "path": "/3"},
+                {"op": "remove", "path": "/2"}
+            ]
+        )"_json;
+
+        CHECK(patch == expected);
+        CHECK(source.patch(patch) == target);
+    }
+
+    SECTION("nested array shrunk")
+    {
+        json const source = {{"a", {0, 1, 2}}};
+        json const target = {{"a", json::array()}};
+
+        json const patch = json::diff(source, target);
+
+        json const expected = R"(
+            [
+                {"op": "remove", "path": "/a/2"},
+                {"op": "remove", "path": "/a/1"},
+                {"op": "remove", "path": "/a/0"}
+            ]
+        )"_json;
+
+        CHECK(patch == expected);
+        CHECK(source.patch(patch) == target);
+    }
+
+    SECTION("many removals still round-trip")
+    {
+        json source = json::array();
+        for (int i = 0; i < 1000; ++i)
+        {
+            source.push_back(i);
+        }
+        json const target = json::array();
+
+        json const patch = json::diff(source, target);
+
+        CHECK(patch.size() == 1000);
+        CHECK(patch.front().at("path") == "/999");
+        CHECK(patch.back().at("path") == "/0");
+        CHECK(source.patch(patch) == target);
+    }
+}