json_view: check_utf8 skips well-formed runs with the parser's string scan

Strings of 32 bytes or more that are written into an editable document
are validated with scan_string_run(), which skips well-formed UTF-8 16
bytes at a time; the byte-wise check runs only from where the scan found
ill-formed UTF-8, to report the same type_error.316. Shorter strings
keep the byte-wise check (inlined with a constant start, so that this
path is the code it was), where the vector scan costs more than it
saves.

set()/push_back() of strings of 32 bytes or more take 0.29-0.76 of the
time (x86-64 GCC, averaged over code layouts) and 0.25-0.80 (AArch64
clang); shorter strings take 1.5-4 % fewer instructions; the json_view
rows of bench_edit execute at most 0.04 % more instructions.

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

include/nlohmann/detail/view/edit.hpp

@@ -26,6 +26,7 @@
 #include <nlohmann/detail/view/lookup.hpp>
 #include <nlohmann/detail/view/macro_scope.hpp>
 #include <nlohmann/detail/view/node.hpp>
+#include <nlohmann/detail/view/scan.hpp>
 #include <nlohmann/detail/view/view_mode.hpp>
 
 NLOHMANN_JSON_NAMESPACE_BEGIN
@@ -46,10 +47,9 @@ struct first_true<false, Conditions...> : std::integral_constant < int, 1 + firs
 /// (type_error.316 with the same message), so that an editable document
 /// only holds valid UTF-8: the error is at the first byte that no
 /// well-formed sequence can continue with (Unicode, Table 3-7).
-inline void check_utf8(const char* s, std::size_t n)
+NLOHMANN_VIEW_ALWAYS_INLINE void check_utf8_bytewise(const unsigned char* p, std::size_t n, std::size_t i)
 {
-    const auto* const p = reinterpret_cast<const unsigned char*>(s); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
+    for (; i < n;)
-    for (std::size_t i = 0; i < n;)
     {
         const unsigned char c = p[i];
         if (c < 0x80)
@@ -79,6 +79,43 @@ inline void check_utf8(const char* s, std::size_t n)
     }
 }
 
+/// The long-string path of check_utf8(): skips well-formed runs with the
+/// parser's string scan (which stops at a quote, a backslash, or a control
+/// character, all legal here, and at ill-formed UTF-8); the byte-wise check
+/// runs only from where the scan found ill-formed UTF-8, to report it.
+NLOHMANN_VIEW_NOINLINE inline void check_utf8_scan(const unsigned char* p, std::size_t n)
+{
+    const unsigned char* const e = p + n;
+    const unsigned char* q = p;
+    for (;;)
+    {
+        q = scan_string_run<true>(q, e);
+        if (q == e)
+        {
+            return;
+        }
+        if (*q >= 0x80)
+        {
+            check_utf8_bytewise(p, n, static_cast<std::size_t>(q - p));
+            return; // not reached: the scan stopped at ill-formed UTF-8
+        }
+        ++q; // a quote, backslash, or control character
+    }
+}
+
+inline void check_utf8(const char* s, std::size_t n)
+{
+    const auto* const p = reinterpret_cast<const unsigned char*>(s); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
+    if (NLOHMANN_VIEW_UNLIKELY(n >= 32))
+    {
+        check_utf8_scan(p, n);
+        return;
+    }
+    // short strings: the vector scan costs more than it saves; (the loop is
+    // inlined with a constant start, so this path is the plain byte-wise check)
+    check_utf8_bytewise(p, n, 0);
+}
+
 /*!
 @brief the edits of an editable basic_json_document
 

single_include/nlohmann/json_view.hpp

@@ -3727,6 +3727,8 @@ NLOHMANN_JSON_NAMESPACE_END
 
 // #include <nlohmann/detail/view/node.hpp>
 
+// #include <nlohmann/detail/view/scan.hpp>
+
 // #include <nlohmann/detail/view/view_mode.hpp>
 //     __ _____ _____ _____
 //  __|  |   __|     |   | |  JSON for Modern C++
@@ -3775,10 +3777,9 @@ struct first_true<false, Conditions...> : std::integral_constant < int, 1 + firs
 /// (type_error.316 with the same message), so that an editable document
 /// only holds valid UTF-8: the error is at the first byte that no
 /// well-formed sequence can continue with (Unicode, Table 3-7).
-inline void check_utf8(const char* s, std::size_t n)
+NLOHMANN_VIEW_ALWAYS_INLINE void check_utf8_bytewise(const unsigned char* p, std::size_t n, std::size_t i)
 {
-    const auto* const p = reinterpret_cast<const unsigned char*>(s); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
+    for (; i < n;)
-    for (std::size_t i = 0; i < n;)
     {
         const unsigned char c = p[i];
         if (c < 0x80)
@@ -3808,6 +3809,43 @@ inline void check_utf8(const char* s, std::size_t n)
     }
 }
 
+/// The long-string path of check_utf8(): skips well-formed runs with the
+/// parser's string scan (which stops at a quote, a backslash, or a control
+/// character, all legal here, and at ill-formed UTF-8); the byte-wise check
+/// runs only from where the scan found ill-formed UTF-8, to report it.
+NLOHMANN_VIEW_NOINLINE inline void check_utf8_scan(const unsigned char* p, std::size_t n)
+{
+    const unsigned char* const e = p + n;
+    const unsigned char* q = p;
+    for (;;)
+    {
+        q = scan_string_run<true>(q, e);
+        if (q == e)
+        {
+            return;
+        }
+        if (*q >= 0x80)
+        {
+            check_utf8_bytewise(p, n, static_cast<std::size_t>(q - p));
+            return; // not reached: the scan stopped at ill-formed UTF-8
+        }
+        ++q; // a quote, backslash, or control character
+    }
+}
+
+inline void check_utf8(const char* s, std::size_t n)
+{
+    const auto* const p = reinterpret_cast<const unsigned char*>(s); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
+    if (NLOHMANN_VIEW_UNLIKELY(n >= 32))
+    {
+        check_utf8_scan(p, n);
+        return;
+    }
+    // short strings: the vector scan costs more than it saves; (the loop is
+    // inlined with a constant start, so this path is the plain byte-wise check)
+    check_utf8_bytewise(p, n, 0);
+}
+
 /*!
 @brief the edits of an editable basic_json_document
 

tests/src/unit-json_view_edit.cpp

@@ -941,3 +941,123 @@ TEST_CASE("json_view edits: duplicate keys")
         CHECK(d.root()["o"]["d"].get<int>() == 0);
     }
 }
+
+#if !defined(JSON_NOEXCEPTION)
+TEST_CASE("json_view edits: check_utf8 agrees with the byte-wise check")
+{
+    namespace dv = nlohmann::detail::view;
+
+    // "ok" or the exception message
+    const auto run = [](bool fast, const std::string & s) -> std::string
+    {
+        try
+        {
+            if (fast)
+            {
+                dv::check_utf8(s.data(), s.size());
+            }
+            else
+            {
+                dv::check_utf8_bytewise(reinterpret_cast<const unsigned char*>(s.data()), s.size(), 0);
+            }
+        }
+        catch (const json::type_error& e)
+        {
+            return {e.what()};
+        }
+        return {"ok"};
+    };
+    std::size_t errors = 0;
+    const auto same = [&](const std::string & s)
+    {
+        const std::string a = run(true, s);
+        const std::string b = run(false, s);
+        if (a != b)
+        {
+            INFO("fast: " << a << ", byte-wise: " << b << ", length " << s.size());
+            CHECK(a == b);
+        }
+        errors += b != "ok" ? 1 : 0;
+    };
+
+    const std::vector<std::string> pieces =
+    {
+        "a", "Z", " ", "\"", "\\", "\n", "\x01", "\x7f", "\xc3\xa4", "\xe4\xb8\xad", "\xf0\x9f\x98\x80",
+        "\x80", "\xbf", "\xc0\x80", "\xc1\xbf", "\xc2", "\xe0\x80\x80", "\xe0\x9f\xbf", "\xed\xa0\x80", "\xed\xbf\xbf",
+        "\xf0\x80\x80\x80", "\xf0\x8f\xbf\xbf", "\xf4\x90\x80\x80", "\xf4\x8f\xbf\xbf", "\xf5", "\xf8", "\xff", "\xfe",
+        "\xe4\xb8", "\xf0\x9f\x98", "\xf0\x9f", "\xf0"
+    };
+
+    // every piece behind prefixes of every length, and followed by more bytes
+    for (std::size_t prefix = 0; prefix <= 64; ++prefix)
+    {
+        for (const auto& piece : pieces)
+        {
+            same(std::string(prefix, 'x') + piece);
+            same(std::string(prefix, 'x') + piece + "yz");
+            same(std::string(prefix, '"') + piece);
+            same(std::string(prefix, '\xc3') + piece);
+            same(std::string(prefix / 2, '\xc3').append(prefix / 2, '\xa4') + piece);
+            same(std::string(prefix, 'x') + "\xe4\xb8\xad" + piece);
+        }
+    }
+    // an invalid byte at every position of valid strings of every length
+    for (std::size_t len = 0; len <= 64; ++len)
+    {
+        const std::string ascii(len, 'a');
+        std::string mixed;
+        while (mixed.size() < len)
+        {
+            if (mixed.size() % 7 == 0)
+            {
+                mixed += "\xc3\xa4";
+            }
+            else if (mixed.size() % 11 == 0)
+            {
+                mixed += "\xf0\x9f\x98\x80";
+            }
+            else
+            {
+                mixed += "a";
+            }
+        }
+        same(ascii);
+        same(mixed);
+        for (std::size_t pos = 0; pos < len; ++pos)
+        {
+            for (const char bad :
+                    {'\x80', '\xc0', '\xc2', '\xe0', '\xf4', '\xff', '"', '\\', '\x1f'
+                    })
+            {
+                std::string s = ascii;
+                s[pos] = bad;
+                same(s);
+                s = mixed;
+                s[pos] = bad;
+                same(s);
+            }
+        }
+    }
+    // random bytes, biased to the interesting ones
+    std::mt19937 gen(5869); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
+    static const std::array<unsigned char, 23> interesting = {{0x00, 0x1f, 0x22, 0x5c, 0x7f, 0x80, 0x8f, 0x90, 0x9f, 0xa0, 0xbf, 0xc0, 0xc2, 0xdf, 0xe0, 0xe1, 0xed, 0xef, 0xf0, 0xf1, 0xf4, 0xf5, 0xff}};
+    for (int i = 0; i < 100000; ++i)
+    {
+        std::string s(gen() % 80, 'a');
+        for (auto& c : s)
+        {
+            const unsigned r = gen() % 8;
+            if (r == 0)
+            {
+                c = static_cast<char>(gen() & 0xff);
+            }
+            else if (r == 1)
+            {
+                c = static_cast<char>(interesting[gen() % interesting.size()]);
+            }
+        }
+        same(s);
+    }
+    CHECK(errors > 1000);
+}
+#endif