Merge branch 'json-view/03-string-scan' into json-view/04-unicode-escapes

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

include/nlohmann/detail/input/lexer.hpp

@@ -221,6 +221,44 @@ class lexer : public lexer_base<BasicJsonType>
     // scan functions
     /////////////////////
 
+    /// contiguous input: try to decode the 4 hex digits following `\u`
+    /// directly from the input buffer via hex_codepoint(), instead of 4 calls
+    /// to get(). On success, advances the adapter and the position counters
+    /// exactly as those 4 get() calls would (a hex digit is never '\n', so
+    /// only the flat counters move) and leaves @a current holding the last of
+    /// the 4 digits, just as the last such get() would; the codepoint is
+    /// written to @a out. Makes no state change and returns false - for a
+    /// pending unget, fewer than 4 remaining bytes, or any of the 4 bytes not
+    /// being a hex digit - so the caller falls back unchanged to the
+    /// per-character loop, which then reports the same diagnostic (stopping
+    /// at the first invalid digit) as before this optimization.
+    bool get_codepoint_bulk(std::true_type /*bulk*/, int& out)
+    {
+        if (next_unget || ia.bulk_remaining() < 4)
+        {
+            return false;
+        }
+        const char_type* const raw = ia.bulk_data();
+        const int codepoint = hex_codepoint(reinterpret_cast<const unsigned char*>(raw));
+        if (codepoint < 0)
+        {
+            return false;
+        }
+        ia.bulk_skip(4);
+        // a hex digit is never a newline, so only the flat counters advance
+        position.chars_read_total += 4;
+        position.chars_read_current_line += 4;
+        current = char_traits<char_type>::to_int_type(raw[3]);
+        out = codepoint;
+        return true;
+    }
+
+    /// streaming input: no bulk fast path
+    bool get_codepoint_bulk(std::false_type /*bulk*/, int& /*out*/) const noexcept
+    {
+        return false;
+    }
+
     /*!
     @brief get codepoint from 4 hex characters following `\\u`
 
@@ -240,6 +278,14 @@ class lexer : public lexer_base<BasicJsonType>
     {
         // this function only makes sense after reading `\u`
         JSON_ASSERT(current == 'u');
+
+        // contiguous input: decode all 4 hex digits directly from the buffer
+        int fast_codepoint = 0;
+        if (get_codepoint_bulk(std::integral_constant<bool, bulk_scan> {}, fast_codepoint))
+        {
+            return fast_codepoint;
+        }
+
         int codepoint = 0;
 
         const auto factors = { 12u, 8u, 4u, 0u };

include/nlohmann/detail/input/string_scan.hpp

@@ -8,8 +8,9 @@
 
 #pragma once
 
+#include <array> // array
 #include <cstddef> // size_t
-#include <cstdint> // uint64_t
+#include <cstdint> // uint64_t, uint8_t
 #include <cstring> // memcpy
 
 #include <nlohmann/detail/bit_ops.hpp>
@@ -315,5 +316,50 @@ inline std::size_t string_bulk_run(const unsigned char* data, std::size_t n) noe
     return scalar_string_bulk_run(data, n);
 }
 
+// Decode the 4 hex digits at [data, data+4) - the digits following a `\u`
+// escape - into a codepoint 0x0000..0xFFFF via one table lookup per byte
+// (after yyjson's read_hex_u16), or return -1 if any of the 4 bytes is not a
+// hex digit ('0'..'9', 'A'..'F', 'a'..'f'). The caller must already have
+// checked that 4 bytes are available; used by lexer::get_codepoint()'s
+// contiguous fast path. On -1 it falls back to the byte-at-a-time loop, which
+// stops at the first invalid digit, so the reported error and position are
+// unaffected by this fast path.
+inline int hex_codepoint(const unsigned char* data) noexcept
+{
+    static const std::array<std::uint8_t, 256> hex_digit_table = // NOLINT(cppcoreguidelines-avoid-non-const-global-variables)
+    {
+        {
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 00..0F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 10..1F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 20..2F
+            0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 30..3F ('0'..'9')
+            0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 40..4F ('A'..'F')
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 50..5F
+            0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 60..6F ('a'..'f')
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 70..7F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 80..8F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 90..9F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // A0..AF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // B0..BF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // C0..CF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // D0..DF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // E0..EF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF  // F0..FF
+        }
+    };
+
+    const std::uint8_t d0 = hex_digit_table[data[0]];
+    const std::uint8_t d1 = hex_digit_table[data[1]];
+    const std::uint8_t d2 = hex_digit_table[data[2]];
+    const std::uint8_t d3 = hex_digit_table[data[3]];
+    // every valid digit is <= 0xF; the combined OR only exceeds it if at
+    // least one of the four bytes was not a hex digit (looked up as 0xFF)
+    if ((d0 | d1 | d2 | d3) > 0x0F)
+    {
+        return -1;
+    }
+    return (d0 << 12) | (d1 << 8) | (d2 << 4) | d3;
+}
+
 }  // namespace detail
 NLOHMANN_JSON_NAMESPACE_END

single_include/nlohmann/json.hpp

@@ -10115,8 +10115,9 @@ NLOHMANN_JSON_NAMESPACE_END
 
 
 
+#include <array> // array
 #include <cstddef> // size_t
-#include <cstdint> // uint64_t
+#include <cstdint> // uint64_t, uint8_t
 #include <cstring> // memcpy
 
 // #include <nlohmann/detail/bit_ops.hpp>
@@ -10424,6 +10425,51 @@ inline std::size_t string_bulk_run(const unsigned char* data, std::size_t n) noe
     return scalar_string_bulk_run(data, n);
 }
 
+// Decode the 4 hex digits at [data, data+4) - the digits following a `\u`
+// escape - into a codepoint 0x0000..0xFFFF via one table lookup per byte
+// (after yyjson's read_hex_u16), or return -1 if any of the 4 bytes is not a
+// hex digit ('0'..'9', 'A'..'F', 'a'..'f'). The caller must already have
+// checked that 4 bytes are available; used by lexer::get_codepoint()'s
+// contiguous fast path. On -1 it falls back to the byte-at-a-time loop, which
+// stops at the first invalid digit, so the reported error and position are
+// unaffected by this fast path.
+inline int hex_codepoint(const unsigned char* data) noexcept
+{
+    static const std::array<std::uint8_t, 256> hex_digit_table = // NOLINT(cppcoreguidelines-avoid-non-const-global-variables)
+    {
+        {
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 00..0F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 10..1F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 20..2F
+            0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 30..3F ('0'..'9')
+            0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 40..4F ('A'..'F')
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 50..5F
+            0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 60..6F ('a'..'f')
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 70..7F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 80..8F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 90..9F
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // A0..AF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // B0..BF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // C0..CF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // D0..DF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // E0..EF
+            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF  // F0..FF
+        }
+    };
+
+    const std::uint8_t d0 = hex_digit_table[data[0]];
+    const std::uint8_t d1 = hex_digit_table[data[1]];
+    const std::uint8_t d2 = hex_digit_table[data[2]];
+    const std::uint8_t d3 = hex_digit_table[data[3]];
+    // every valid digit is <= 0xF; the combined OR only exceeds it if at
+    // least one of the four bytes was not a hex digit (looked up as 0xFF)
+    if ((d0 | d1 | d2 | d3) > 0x0F)
+    {
+        return -1;
+    }
+    return (d0 << 12) | (d1 << 8) | (d2 << 4) | d3;
+}
+
 }  // namespace detail
 NLOHMANN_JSON_NAMESPACE_END
 
@@ -10630,6 +10676,44 @@ class lexer : public lexer_base<BasicJsonType>
     // scan functions
     /////////////////////
 
+    /// contiguous input: try to decode the 4 hex digits following `\u`
+    /// directly from the input buffer via hex_codepoint(), instead of 4 calls
+    /// to get(). On success, advances the adapter and the position counters
+    /// exactly as those 4 get() calls would (a hex digit is never '\n', so
+    /// only the flat counters move) and leaves @a current holding the last of
+    /// the 4 digits, just as the last such get() would; the codepoint is
+    /// written to @a out. Makes no state change and returns false - for a
+    /// pending unget, fewer than 4 remaining bytes, or any of the 4 bytes not
+    /// being a hex digit - so the caller falls back unchanged to the
+    /// per-character loop, which then reports the same diagnostic (stopping
+    /// at the first invalid digit) as before this optimization.
+    bool get_codepoint_bulk(std::true_type /*bulk*/, int& out)
+    {
+        if (next_unget || ia.bulk_remaining() < 4)
+        {
+            return false;
+        }
+        const char_type* const raw = ia.bulk_data();
+        const int codepoint = hex_codepoint(reinterpret_cast<const unsigned char*>(raw));
+        if (codepoint < 0)
+        {
+            return false;
+        }
+        ia.bulk_skip(4);
+        // a hex digit is never a newline, so only the flat counters advance
+        position.chars_read_total += 4;
+        position.chars_read_current_line += 4;
+        current = char_traits<char_type>::to_int_type(raw[3]);
+        out = codepoint;
+        return true;
+    }
+
+    /// streaming input: no bulk fast path
+    bool get_codepoint_bulk(std::false_type /*bulk*/, int& /*out*/) const noexcept
+    {
+        return false;
+    }
+
     /*!
     @brief get codepoint from 4 hex characters following `\\u`
 
@@ -10649,6 +10733,14 @@ class lexer : public lexer_base<BasicJsonType>
     {
         // this function only makes sense after reading `\u`
         JSON_ASSERT(current == 'u');
+
+        // contiguous input: decode all 4 hex digits directly from the buffer
+        int fast_codepoint = 0;
+        if (get_codepoint_bulk(std::integral_constant<bool, bulk_scan> {}, fast_codepoint))
+        {
+            return fast_codepoint;
+        }
+
         int codepoint = 0;
 
         const auto factors = { 12u, 8u, 4u, 0u };

tests/src/unit-class_lexer.cpp

@@ -18,6 +18,7 @@ using nlohmann::json;
 #include <cstdlib> // strtod
 #include <cstring> // memcpy
 #include <map> // map
+#include <random> // mt19937
 #include <sstream> // stringstream
 #include <string> // string
 #include <utility> // pair
@@ -664,6 +665,184 @@ TEST_CASE("lexer string fast path")
     }
 }
 
+TEST_CASE("lexer escape fast path")
+{
+    // json::accept() never throws, so this section stays covered without
+    // exceptions; it pins which of the cases below are valid/invalid and
+    // checks the contiguous and streaming paths agree on that classification.
+    SECTION("accept() parity")
+    {
+        const std::vector<std::pair<std::string, bool>> cases =
+        {
+            {"\\u0041", true}, {"\\u00e4", true}, {"\\u00E4", true},
+            {"\\uD83D\\uDE00", true},
+            {"\\u12", false}, {"\\u12G4", false}, {"\\uXYZW", false},
+            {"\\uD800", false}, {"\\uD800A", false}, {"\\uD800\\u0041", false},
+            {"\\uDC00", false}, {"\\u", false}
+        };
+
+        for (const auto& c : cases)
+        {
+            for (const std::size_t offset :
+                    {
+                        std::size_t{0}, std::size_t{9}
+                    })
+            {
+                const std::string doc = "[\"" + std::string(offset, 'a') + c.first + "\"]";
+                CAPTURE(doc);
+                CHECK(json::accept(doc) == c.second);
+                std::stringstream ss(doc);
+                CHECK(json::accept(ss) == c.second);
+            }
+        }
+    }
+
+#if !defined(JSON_NOEXCEPTION)
+    // the full outcome of parsing @a doc: the parsed value, or the exact
+    // error message, so a mismatch in either is caught
+    const auto outcome = [](const std::string & doc, bool streaming) -> std::string
+    {
+        try
+        {
+            if (streaming)
+            {
+                std::stringstream ss(doc);
+                const json j = json::parse(ss);
+                return j.dump();
+            }
+            const json j = json::parse(doc);
+            return j.dump();
+        }
+        catch (const json::exception& e)
+        {
+            return {e.what()};
+        }
+    };
+
+    SECTION("contiguous vs streaming parity")
+    {
+        const std::vector<std::string> escapes =
+        {
+            "\\u0041",             // "A"
+            "\\u00e4",             // "ä" (lowercase hex)
+            "\\u00E4",             // "ä" (uppercase hex)
+            "\\uD83D\\uDE00",      // valid surrogate pair (an emoji)
+            "\\u12",               // truncated: only 2 hex digits before the closing quote
+            "\\u12G4",             // invalid hex digit at the 3rd position
+            "\\uXYZW",             // all 4 bytes invalid
+            "\\uD800",             // lone high surrogate, string ends right after
+            "\\uD800A",            // high surrogate not followed by another \u escape
+            "\\uD800\\u0041",      // high surrogate followed by \u, but not a low surrogate
+            "\\uDC00",             // lone low surrogate
+            "\\u",                 // '\u' with nothing after (closing quote right away)
+        };
+
+        // once at the start of the string and once past the first 8-byte SWAR
+        // word of the outer string_bulk_run, so the escape is reached both
+        // right after the opening quote and mid-run
+        for (const auto& escape : escapes)
+        {
+            for (const std::size_t offset :
+                    {
+                        std::size_t{0}, std::size_t{9}
+                    })
+            {
+                const std::string doc = "[\"" + std::string(offset, 'a') + escape + "\"]";
+                CAPTURE(doc);
+                CHECK(outcome(doc, false) == outcome(doc, true));
+            }
+
+            // the escape is the last thing before end of input: no closing
+            // quote at all
+            const std::string truncated_doc = "[\"" + escape;
+            CAPTURE(truncated_doc);
+            CHECK(outcome(truncated_doc, false) == outcome(truncated_doc, true));
+        }
+    }
+
+    SECTION("truncated \\u escape at every distance from the end of input")
+    {
+        // ia.bulk_remaining() must correctly report fewer than 4 bytes for
+        // every possible count of trailing hex-looking bytes (0, 1, 2, or 3)
+        // before end of input, so the fast path declines and the byte path
+        // alone reports the "must be followed by 4 hex digits" error, at the
+        // same position, in every case
+        for (const std::string& tail :
+                {
+                    std::string{}, std::string("1"), std::string("12"), std::string("123")
+                })
+        {
+            const std::string doc = "[\"\\u" + tail;
+            CAPTURE(doc);
+            CHECK(outcome(doc, false) == outcome(doc, true));
+            CHECK(outcome(doc, false).find("must be followed by 4 hex digits") != std::string::npos);
+        }
+    }
+
+    SECTION("invalid hex digit at every position of the 4")
+    {
+        // the fast path must decline for *any* invalid byte among the 4, not
+        // just the first, and the byte path must then stop at exactly that
+        // position - same as it always has
+        for (std::size_t bad_pos = 0; bad_pos < 4; ++bad_pos)
+        {
+            std::string digits = "1234";
+            digits[bad_pos] = 'g'; // not a hex digit
+            const std::string doc = "[\"\\u" + digits + "\"]";
+            CAPTURE(doc);
+            CHECK(outcome(doc, false) == outcome(doc, true));
+            CHECK(outcome(doc, false).find("must be followed by 4 hex digits") != std::string::npos);
+        }
+    }
+
+    SECTION("random escapes")
+    {
+        // A seeded PRNG builds the 4 bytes following `\u` from a mix of hex
+        // digits and non-hex bytes, at varying distances from the start of
+        // the string, to compare the two scanners on many more shapes than
+        // are practical to enumerate by hand.
+        std::mt19937 gen(7654321); // NOLINT(cert-msc32-c,cert-msc51-cpp)
+        const std::string hex_alphabet = "0123456789AaBbCcDdEeFf";
+        std::uniform_int_distribution<std::size_t> pick_hex(0, hex_alphabet.size() - 1);
+        std::uniform_int_distribution<int> pick_byte(1, 255); // never NUL
+        std::uniform_int_distribution<int> pick_is_hex(0, 4); // 4-in-5 chance of a hex digit
+        std::uniform_int_distribution<std::size_t> pick_offset(0, 12);
+
+        std::vector<std::string> mismatches;
+        for (int iter = 0; iter < 3000; ++iter)
+        {
+            std::string digits;
+            for (int i = 0; i < 4; ++i)
+            {
+                if (pick_is_hex(gen) != 0)
+                {
+                    digits += hex_alphabet[pick_hex(gen)];
+                }
+                else
+                {
+                    char c = static_cast<char>(pick_byte(gen));
+                    if (c == '"' || c == '\\')
+                    {
+                        // keep the string well-formed apart from the escape
+                        // itself, so any mismatch is attributable to the \u
+                        // handling and not to an unrelated quote/escape
+                        c = 'z';
+                    }
+                    digits += c;
+                }
+            }
+            const std::string doc = "[\"" + std::string(pick_offset(gen), 'a') + "\\u" + digits + "\"]";
+            if (outcome(doc, false) != outcome(doc, true))
+            {
+                mismatches.push_back(doc);
+            }
+        }
+        CAPTURE(mismatches);
+        CHECK(mismatches.empty());
+    }
+#endif
+}
+
 namespace
 {
 // the index of the decimal point (or npos) and of the end of the mantissa of a