Rename the key index's match callback so Flawfinder doesn't read it as std::equal

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

include/nlohmann/detail/input/binary_reader.hpp

@@ -86,7 +86,7 @@ JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 2
 /*!
 @brief deserialization of BJData, BON8, BSON, CBOR, MessagePack, and UBJSON values
 */
-template<typename BasicJsonType, typename InputAdapterType, typename SAX = json_sax_dom_parser<BasicJsonType, InputAdapterType>>
+template<typename BasicJsonType, typename InputAdapterType, typename SAX = json_sax_dom_binary_parser<BasicJsonType, InputAdapterType>>
 class binary_reader
 {
     using number_integer_t = typename BasicJsonType::number_integer_t;

include/nlohmann/detail/input/lexer.hpp

@@ -14,6 +14,7 @@
 #include <cstdio> // snprintf
 #include <cstring> // memcmp
 #include <initializer_list> // initializer_list
+#include <limits> // numeric_limits
 #include <string> // char_traits, string
 #include <utility> // move
 #include <vector> // vector
@@ -1816,6 +1817,15 @@ scan_number_done:
     /// significand (see scan_number_bulk_contiguous())
     bool convert_accumulated_float(const float_significand& s, std::true_type /*native*/) noexcept
     {
+        // accept() only needs to know that the value is finite (see the parser):
+        // w < 10^19, so a value below 10^max_exponent10 cannot overflow, and a
+        // value that underflows is a finite number as well. Only a token that
+        // may overflow has to be converted to find out.
+        if (JSON_HEDLEY_UNLIKELY(discard_number_values && s.exponent + 19 <= std::numeric_limits<number_float_t>::max_exponent10))
+        {
+            value_float = 0;
+            return true;
+        }
         value_float = decimal_to_float<number_float_t>(s);
         return true;
     }

include/nlohmann/detail/input/parser.hpp

@@ -250,6 +250,13 @@ class parser
         // value to avoid a goto (see comment where set to true)
         bool skip_to_state_evaluation = false;
 
+        // a document that starts with a container pushes onto the stack at
+        // once: allocate it in one step instead of growing it from 1 byte
+        if (last_token == token_type::begin_object || last_token == token_type::begin_array)
+        {
+            states.reserve(32);
+        }
+
         while (true)
         {
             if (!skip_to_state_evaluation)

include/nlohmann/detail/json_pointer.hpp

@@ -8,7 +8,7 @@
 
 #pragma once
 
-#include <algorithm> // all_of, copy
+#include <algorithm> // all_of
 #include <array> // array
 #include <cctype> // isdigit
 #include <cerrno> // errno, ERANGE
@@ -82,34 +82,12 @@ class json_pointer
     {
         // one buffer: every token adds its escaped form (at least its length) and a slash
         std::size_t length = 0;
-        bool plain = true;
         for (const auto& reference_token : reference_tokens)
         {
             length += reference_token.size() + 1;
-            const char* const data = reference_token.data();
-            for (std::size_t i = 0, size = reference_token.size(); plain && i < size; ++i)
-            {
-                plain = data[i] != '~' && data[i] != '/';
-            }
         }
 
         string_t result;
-        if (JSON_HEDLEY_LIKELY(plain))
-        {
-            // nothing to escape: the tokens are copied into the string
-            result.resize(length);
-            if (length != 0)
-            {
-                char* out = &result[0];
-                for (const auto& reference_token : reference_tokens)
-                {
-                    *out++ = '/';
-                    out = std::copy(reference_token.data(), reference_token.data() + reference_token.size(), out);
-                }
-            }
-            return result;
-        }
-
         result.reserve(length);
         for (const auto& reference_token : reference_tokens)
         {
@@ -1220,32 +1198,33 @@ class json_pointer
         }
         result.reserve(token_count);
 
-        // extract the reference tokens: every one runs from after a slash to
-        // the next slash or the end of the string; a token without a '~' (the
-        // common case) is stored as it is, others are checked and unescaped
-        const char* const data = reference_string.data();
-        const char* const end = data + size;
-        for (const char* start = data + 1;; ++start)
+        // extract the reference tokens:
+        // - slash: position of the last read slash (or end of string)
+        // - start: position after the previous slash
+        for (
+            // search for the first slash after the first character
+            std::size_t slash = reference_string.find_first_of('/', 1),
+            // set the beginning of the first reference token
+            start = 1;
+            // we can stop if start == 0 (if slash == string_t::npos)
+            start != 0;
+            // set the beginning of the next reference token
+            // (will eventually be 0 if slash == string_t::npos)
+            start = (slash == string_t::npos) ? 0 : slash + 1,
+            // find next slash
+            slash = reference_string.find_first_of('/', start))
         {
-            const char* slash = start;
-            bool escaped = false;
-            while (slash != end && *slash != '/')
-            {
-                escaped = escaped || *slash == '~';
-                ++slash;
-            }
+            // use the text between the beginning of the reference token
+            // (start) and the last slash (slash).
+            const auto count = (slash == string_t::npos ? reference_string.size() : slash) - start;
+            auto reference_token = string_t(reference_string.data() + start, count);
 
-            const auto count = static_cast<std::size_t>(slash - start);
-            if (JSON_HEDLEY_LIKELY(!escaped))
+            // check reference tokens are properly escaped; a token without
+            // a '~' (the common case) needs neither check nor unescaping
+            std::size_t pos = reference_token.find_first_of('~');
+            if (pos != string_t::npos)
             {
-                result.emplace_back(start, count);
-            }
-            else
-            {
-                auto reference_token = string_t(start, count);
-
-                // check reference tokens are properly escaped
-                for (std::size_t pos = reference_token.find_first_of('~'); pos != string_t::npos; pos = reference_token.find_first_of('~', pos + 1))
+                for (; pos != string_t::npos; pos = reference_token.find_first_of('~', pos + 1))
                 {
                     JSON_ASSERT(reference_token[pos] == '~');
 
@@ -1259,14 +1238,10 @@ class json_pointer
                 }
 
                 detail::unescape(reference_token);
-                result.push_back(std::move(reference_token));
             }
 
-            if (slash == end)
-            {
-                break;
-            }
-            start = slash;
+            // finally, store the reference token
+            result.push_back(std::move(reference_token));
         }
 
         return result;

include/nlohmann/json.hpp

@@ -161,6 +161,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     template<typename BasicJsonType, typename InputAdapterType>
     friend class ::nlohmann::detail::json_sax_dom_parser;
     template<typename BasicJsonType, typename InputAdapterType>
+    friend class ::nlohmann::detail::json_sax_dom_binary_parser;
+    template<typename BasicJsonType, typename InputAdapterType>
     friend class ::nlohmann::detail::json_sax_dom_callback_parser;
 #if JSON_DIAGNOSTIC_POSITIONS
     friend struct ::nlohmann::detail::diagnostic_positions;
@@ -6287,7 +6289,7 @@ public:
            from_ubjson/from_bjdata/from_bon8/from_bson overloads
 
     Building the @ref binary_reader as a named local, rather than as a
-    temporary that @ref detail::json_sax_dom_parser::parse is called on in
+    temporary that @ref detail::json_sax_dom_binary_parser::parse is called on in
     the same expression, avoids a false-positive cppcheck accessMoved
     warning in each of the 16 callers.
     */
@@ -6298,7 +6300,7 @@ public:
                                        const cbor_tag_handler_t tag_handler = cbor_tag_handler_t::error)
     {
         basic_json result;
-        detail::json_sax_dom_parser<basic_json, InputAdapterType> sdp(result, allow_exceptions);
+        detail::json_sax_dom_binary_parser<basic_json, InputAdapterType> sdp(result, allow_exceptions);
         binary_reader<InputAdapterType> reader(std::move(ia), format, error_handler);
         if (!reader.sax_parse(&sdp, strict, tag_handler))
         {

tests/src/unit-class_parser.cpp

@@ -2952,3 +2952,32 @@ TEST_CASE("diagnostic positions: value lifetime, input adapters, and SAX")
     }
 }
 #endif
+
+TEST_CASE("accept() agrees with parse() on floats around the overflow limit")
+{
+    // accept() does not convert a float that cannot overflow; the tokens
+    // around the limit (and beyond it) must still be rejected exactly as
+    // parse() rejects them
+    const char* const numbers[] =
+    {
+        "1e0", "123.456e-5", "1e-400", "-1e-400", "1e307", "1e308", "1e309", "-1e309",
+        "10e307", "100e307", "0.1e309", "0.1e310", "1E+308", "1E+309",
+        "1.7976931348623157e308", "1.7976931348623159e308", "1.8e308", "-1.7976931348623157e308",
+        "12345678901234567e291", "12345678901234567e292", "123456789012345678e290", "123456789012345678e291",
+        "1234567890123456789e289", "1234567890123456789e290", "9999999999999999999e289", "9999999999999999999e290",
+        "0.00000000000000000001e328", "0.00000000000000000001e329"
+    };
+
+    for (const char* number : numbers)
+    {
+        for (const std::string text :
+                {
+                    std::string(number), "[" + std::string(number) + "]", "{\"a\":" + std::string(number) + "}"
+                })
+        {
+            INFO(text);
+            const bool parses = !json::parse(text, nullptr, false).is_discarded();
+            CHECK(json::accept(text) == parses);
+        }
+    }
+}

tests/src/unit-ordered_json.cpp

@@ -237,3 +237,274 @@ TEST_CASE("regression test for issue #5673 - ordered_json::emplace with a non-rv
         CHECK(oj.dump() == "{\"a\":1}");
     }
 }
+
+namespace
+{
+// the sizes around which the DOM parser changes how it stores the elements of
+// an array (16) and the members of an object in a vector (32, and 64 for the
+// key index)
+const std::size_t container_sizes[] = {0, 1, 2, 3, 15, 16, 17, 18, 31, 32, 33, 34, 63, 64, 65, 66, 200};
+
+template<typename Json>
+std::string array_text(const std::size_t n, const std::size_t depth)
+{
+    std::string text = "[";
+    for (std::size_t i = 0; i < n; ++i)
+    {
+        text += (i == 0 ? "" : ",");
+        // alternate scalars, empty containers and nested containers
+        switch (i % 4)
+        {
+            case 0:
+                text += std::to_string(i);
+                break;
+            case 1:
+                text += "\"s" + std::to_string(i) + "\"";
+                break;
+            case 2:
+                text += depth == 0 ? "[]" : array_text<Json>(n / 2, depth - 1);
+                break;
+            default:
+                text += depth == 0 ? "{}" : "{\"a\":" + array_text<Json>(n / 3, depth - 1) + ",\"b\":null}";
+                break;
+        }
+    }
+    return text + "]";
+}
+
+template<typename Json>
+std::string object_text(const std::size_t n, const std::size_t depth, const bool duplicates)
+{
+    std::string text = "{";
+    for (std::size_t i = 0; i < n; ++i)
+    {
+        text += (i == 0 ? "" : ",");
+        text += "\"key" + std::to_string(i) + "\":";
+        switch (i % 4)
+        {
+            case 0:
+                text += std::to_string(i);
+                break;
+            case 1:
+                text += depth == 0 ? "[]" : array_text<Json>(n / 2, depth - 1);
+                break;
+            case 2:
+                text += depth == 0 ? "{}" : object_text<Json>(n / 2, depth - 1, duplicates);
+                break;
+            default:
+                text += "\"value\"";
+                break;
+        }
+    }
+    if (duplicates)
+    {
+        // keys that are there already, the first and the last one, with other values
+        text += n == 0 ? "" : ",";
+        text += "\"key0\":[1,2],\"key" + std::to_string(n - 1) + "\":{\"again\":true}";
+    }
+    return text + "}";
+}
+
+template<typename Json>
+void check_same_dump(const std::string& text)
+{
+    // the text is what dump() writes for the parsed value, and the value
+    // survives a second round trip: arrays keep their elements in order, an
+    // ordered_json keeps its members in order of appearance
+    const Json parsed = Json::parse(text);
+    const Json again = Json::parse(parsed.dump());
+    CHECK(parsed == again);
+    CHECK(parsed.dump() == again.dump());
+    CHECK(Json::accept(text));
+}
+} // namespace
+
+TEST_CASE("parsing containers of sizes around the limits of the DOM parser")
+{
+    SECTION("arrays")
+    {
+        for (const std::size_t n : container_sizes)
+        {
+            const std::string text = array_text<json>(n, 2);
+            INFO("size ", n);
+
+            const json parsed = json::parse(text);
+            CHECK(parsed.is_array());
+            CHECK(parsed.size() == n);
+            for (std::size_t i = 0; i < n; i += 4)
+            {
+                CHECK(parsed[i] == i);
+            }
+            check_same_dump<json>(text);
+            check_same_dump<ordered_json>(text);
+            CHECK(ordered_json::parse(text).dump() == parsed.dump());
+        }
+    }
+
+    SECTION("objects")
+    {
+        for (const bool duplicates :
+                {
+                    false, true
+                })
+        {
+            for (const std::size_t n : container_sizes)
+            {
+                const std::string text = object_text<json>(n, 2, duplicates);
+                INFO("size ", n, " duplicates ", duplicates);
+
+                const json parsed = json::parse(text);
+                const ordered_json ordered = ordered_json::parse(text);
+                CHECK(parsed.is_object());
+                CHECK(ordered.is_object());
+                CHECK(parsed.size() == ordered.size());
+                // the same members, in the order of their first appearance
+                std::size_t i = 0;
+                for (auto it = ordered.begin(); it != ordered.end(); ++it, ++i)
+                {
+                    if (i < n)
+                    {
+                        CHECK(it.key() == "key" + std::to_string(i));
+                    }
+                    CHECK(parsed.at(it.key()) == json(it.value()));
+                }
+                if (duplicates && n > 1)
+                {
+                    // the later value replaced the earlier one in its place
+                    CHECK(ordered.at("key0") == ordered_json::parse("[1,2]"));
+                    CHECK(ordered.at("key" + std::to_string(n - 1)) == ordered_json::parse("{\"again\":true}"));
+                    CHECK(ordered.begin().key() == "key0");
+                    CHECK(ordered.size() == n);
+                }
+                check_same_dump<json>(text);
+                check_same_dump<ordered_json>(text);
+            }
+        }
+    }
+
+    SECTION("objects with many different and repeated keys")
+    {
+        // 300 members of which a third repeat an earlier key
+        std::string text = "{";
+        for (std::size_t i = 0; i < 300; ++i)
+        {
+            text += (i == 0 ? "" : ",");
+            text += "\"k" + std::to_string(i % 200) + "\":" + std::to_string(i);
+        }
+        text += "}";
+
+        const ordered_json ordered = ordered_json::parse(text);
+        const json parsed = json::parse(text);
+        CHECK(ordered.size() == 200);
+        CHECK(parsed.size() == 200);
+        std::size_t i = 0;
+        for (auto it = ordered.begin(); it != ordered.end(); ++it, ++i)
+        {
+            CHECK(it.key() == "k" + std::to_string(i));
+            // the last value written
+            CHECK(it.value() == (i < 100 ? i + 200 : i));
+            CHECK(parsed.at(it.key()) == json(it.value()));
+        }
+    }
+}
+
+namespace
+{
+// a deterministic source of structure for parsing tests: builds a JSON text
+// and, at the same time, the value it has to parse to
+class tree_generator
+{
+  public:
+    explicit tree_generator(std::uint32_t seed) : state(seed) {}
+
+    template<typename Json>
+    Json make(std::string& text, const std::size_t depth)
+    {
+        switch (next(depth == 0 ? 5 : 9))
+        {
+            case 0:
+                text += "null";
+                return Json(nullptr);
+            case 1:
+                text += "true";
+                return Json(true);
+            case 2:
+            {
+                const int n = static_cast<int>(next(2000)) - 1000;
+                text += std::to_string(n);
+                return Json(n);
+            }
+            case 3:
+                text += "\"text\"";
+                return Json("text");
+            case 4:
+                text += "2.5";
+                return Json(2.5);
+            case 5:
+            case 6:
+            case 7:
+            {
+                Json array = Json::array();
+                text += "[";
+                const std::size_t n = size();
+                for (std::size_t i = 0; i < n; ++i)
+                {
+                    text += (i == 0 ? "" : ",");
+                    array.push_back(make<Json>(text, depth - 1));
+                }
+                text += "]";
+                return array;
+            }
+            default:
+            {
+                Json object = Json::object();
+                text += "{";
+                const std::size_t n = size();
+                for (std::size_t i = 0; i < n; ++i)
+                {
+                    const std::string key = "k" + std::to_string(i);
+                    text += (i == 0 ? "\"" : ",\"") + key + "\":";
+                    object[key] = make<Json>(text, depth - 1);
+                }
+                text += "}";
+                return object;
+            }
+        }
+    }
+
+  private:
+    std::uint32_t next(const std::uint32_t bound)
+    {
+        state = state * 1664525U + 1013904223U;
+        return (state >> 8) % bound;
+    }
+
+    std::size_t size()
+    {
+        return container_sizes[next(sizeof(container_sizes) / sizeof(*container_sizes))];
+    }
+
+    std::uint32_t state;
+};
+} // namespace
+
+TEST_CASE("parsing random trees of arrays and objects")
+{
+    for (std::uint32_t seed = 1; seed <= 150; ++seed)
+    {
+        INFO("seed ", seed);
+
+        std::string text;
+        std::string ordered_text;
+        const json expected = tree_generator(seed).make<json>(text, 3);
+        const ordered_json ordered_expected = tree_generator(seed).make<ordered_json>(ordered_text, 3);
+        CHECK(text == ordered_text);
+
+        CHECK(json::parse(text) == expected);
+        CHECK(json::accept(text));
+        const ordered_json ordered = ordered_json::parse(text);
+        CHECK(ordered == ordered_expected);
+        CHECK(ordered.dump() == ordered_expected.dump());
+        CHECK(json::parse(text).dump() == expected.dump());
+    }
+}