tests/src/unit-json_view_builder.cpp

//     __ _____ _____ _____
//  __|  |   __|     |   | |  JSON for Modern C++ (supporting code)
// |  |  |__   |  |  | | | |  version 3.12.0
// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
//
// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
// SPDX-License-Identifier: MIT

#include "doctest_compatibility.h"

#include <nlohmann/json.hpp>
#if JSON_TEST_USING_MULTIPLE_HEADERS
    #include <nlohmann/detail/view/builder.hpp>
    #include <nlohmann/detail/view/materialize.hpp>
    #include <nlohmann/detail/view/string_ref.hpp>
    #include <nlohmann/json_view.hpp> // json_document::accept
#else
    #include <nlohmann/json_view.hpp> // the single header contains the internal headers
#endif
using nlohmann::json;

#include <array>
#include <cstdint>
#include <fstream>
#include <limits>
#include <map>
#include <memory>
#include <new>
#include <random>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#include <test_data.hpp>

namespace
{
using nlohmann::detail::view::document_data;
using nlohmann::detail::view::node;

// the node index of a text; a vector input has no terminating NUL, so that
// AddressSanitizer catches any read past the last byte
struct built
{
    std::unique_ptr<document_data, document_data::deleter> data{}; // NOLINT(readability-redundant-member-init)
    std::vector<char> copy{}; // NOLINT(readability-redundant-member-init)
    bool ok = false;
    nlohmann::detail::view::parse_failure failure{};
};

template<typename FloatType = double>
built build(const std::string& text, bool comments, bool trailing_commas, bool sentinel)
{
    built r;
    r.data.reset(document_data::create(nlohmann::detail::view::estimate_nodes(text.data(), text.size())));
    const char* src = text.c_str();
    if (!sentinel)
    {
        r.copy.assign(text.begin(), text.end());
        src = r.copy.data();
    }
    constexpr bool nul_is_end = !nlohmann::detail::abi_config::strict_nul_handling;
    r.ok = nlohmann::detail::view::build<FloatType, nul_is_end>(*r.data, src, text.size(), comments, trailing_commas, sentinel, false, r.failure);
    r.data->src = src;
    r.data->base[0] = src;
    r.data->base[1] = r.data->arena.data();
    return r;
}

// the value of a subtree, as json::parse would build it
json value_of(const document_data& d, const node*& n)
{
    const node& x = *n;
    ++n;
    switch (static_cast<json::value_t>(x.kind))
    {
        case json::value_t::object:
        {
            json o = json::object();
            const node* const end = &x + x.next;
            while (n != end)
            {
                const std::string key(d.str(*n), n->len);
                ++n;
                o[key] = value_of(d, n);
            }
            return o;
        }
        case json::value_t::array:
        {
            json a = json::array();
            const node* const end = &x + x.next;
            while (n != end)
            {
                a.push_back(value_of(d, n));
            }
            return a;
        }
        case json::value_t::string:
            return std::string(d.str(x), x.len);
        case json::value_t::boolean:
            return (x.flags & nlohmann::detail::view::node_flags::is_true) != 0;
        case json::value_t::number_integer:
            return static_cast<std::int64_t>(nlohmann::detail::view::integer_bits(x));
        case json::value_t::number_unsigned:
            return nlohmann::detail::view::integer_bits(x);
        case json::value_t::number_float:
            return json::parse(std::string(d.src + x.off, x.len)).get<double>();
        case json::value_t::null:
        case json::value_t::binary:
        case json::value_t::discarded:
        default:
            return nullptr;
    }
}

json value_of(const built& b)
{
    const node* n = b.data->nodes;
    json v = value_of(*b.data, n);
    CHECK(n == b.data->nodes + b.data->node_count);
    return v;
}

// accept/reject and the value must match json::parse, for all options and
// with and without a NUL after the text
void check_same(const std::string& text)
{
    CAPTURE(text)
    for (int options = 0; options < 4; ++options)
    {
        const bool comments = (options & 1) != 0;
        const bool trailing_commas = (options & 2) != 0;
        const bool accepted = json::accept(text, comments, trailing_commas);
        for (const bool sentinel :
                {
                    true, false
                })
        {
            const built b = build(text, comments, trailing_commas, sentinel);
            CHECK(b.ok == accepted);
            if (b.ok && accepted)
            {
                CHECK(value_of(b) == json::parse(text, nullptr, true, comments, trailing_commas));
            }
        }
    }
}

// a string value and a key must be accepted or rejected as json::parse does,
// and give its value (cheaper than check_same: the options do not matter)
void check_string(const std::string& content)
{
    for (const std::string& text :
            {
                "[\"" + content + "\"]", "{\"" + content + "\":1}"
            })
    {
        const bool accepted = json::accept(text);
        for (const bool sentinel :
                {
                    true, false
                })
        {
            const built b = build(text, false, false, sentinel);
            if (b.ok != accepted || (accepted && value_of(b) != json::parse(text)))
            {
                CAPTURE(text)
                CHECK(b.ok == accepted);
                CHECK((b.ok && accepted ? value_of(b) == json::parse(text) : true));
            }
        }
    }
}

// accept() stores no nodes: it must accept and reject what json::accept does, for all options and for inputs with
// and without a terminating NUL
void check_accept(const std::string& text)
{
    CAPTURE(text)
    const std::vector<char> bytes(text.begin(), text.end());
    for (int options = 0; options < 4; ++options)
    {
        const bool comments = (options & 1) != 0;
        const bool trailing_commas = (options & 2) != 0;
        const bool accepted = json::accept(text, comments, trailing_commas);
        CHECK(nlohmann::json_document::accept(text, comments, trailing_commas) == accepted);
        CHECK(nlohmann::json_document::accept(bytes, comments, trailing_commas) == accepted);
    }
}

// a small deterministic generator of documents
struct generator
{
    std::mt19937 rng{5295}; // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed)

    int r(int n)
    {
        return static_cast<int>(rng() % static_cast<unsigned>(n));
    }

    void ws(std::string& o)
    {
        for (int n = r(4) == 0 ? r(12) : r(2); n > 0; --n)
        {
            o += " \n\t\r  "[r(6)];
        }
    }

    void str(std::string& o)
    {
        static const char* const pieces[] = {"a", "Z", " ", "~", "\\n", "\\\"", "\\\\", "\\/", "\\u00e9", "\\ud83d\\ude00", "\xc3\xa9", "\xe3\x81\x82", "\xf0\x9f\x98\x80", "\x7f", "\\u001f", "long enough text to leave the first 16 bytes"}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
        o += '"';
        for (int n = r(3) == 0 ? r(20) : r(6); n > 0; --n)
        {
            o += pieces[r(16)];
        }
        o += '"';
    }

    void num(std::string& o)
    {
        static const char* const numbers[] = {"0", "-0", "1", "-1", "12", "123456789", "1234567890123456789", "9223372036854775807", "-9223372036854775808", // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
                                              "9223372036854775808", "18446744073709551615", "18446744073709551616", "-9223372036854775809",
                                              "1.5", "-2.25e-3", "1e10", "1E+2", "0.000001", "3.141592653589793238462643", "1e308", "-1e-400", "123.456e7"
                                             };
        o += numbers[r(22)];
    }

    void value(std::string& o, int depth)
    {
        ws(o);
        const int k = depth > 5 ? 2 + r(6) : r(8);
        if (k == 0 || k == 1)
        {
            const bool object = k == 0;
            o += object ? '{' : '[';
            for (int i = r(5); i > 0; --i)
            {
                ws(o);
                if (object)
                {
                    str(o);
                    ws(o);
                    o += ':';
                }
                value(o, depth + 1);
                o += i > 1 ? "," : "";
            }
            ws(o);
            o += object ? '}' : ']';
        }
        else if (k < 4)
        {
            str(o);
        }
        else if (k < 6)
        {
            num(o);
        }
        else
        {
            static const char* const literals[] = {"true", "false", "null"}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
            o += literals[r(3)];
        }
        ws(o);
    }
};
} // namespace

TEST_CASE("json_view string_ref")
{
    // std::string_view in C++17, a stand-in with the same members before
    using nlohmann::detail::view::string_ref;
    const std::string text = "abc";
    const string_ref r(text);
    CHECK(r.length() == 3);
    CHECK(std::string(r.begin(), r.end()) == "abc");
    CHECK(r[1] == 'b');
    CHECK(r != string_ref("abd"));
    CHECK_FALSE(r != string_ref("abcd", 3));
    std::ostringstream o;
    o << r;
    CHECK(o.str() == "abc");
}

TEST_CASE("json_view builder")
{
    SECTION("scalars and containers")
    {
        for (const char* text :
                {
                    "null", "true", "false", "0", "-0", "42", "-42", "1.5", "\"\"", "\"abc\"", "[]", "{}", "[1,2,3]", "{\"a\":1,\"b\":[true,null]}", // NOLINT(modernize-raw-string-literal)
                    " [ 1 , 2 ] ", "{\"a\" : {\"b\" : {}}}", "[[[]]]", "\"\\u00e4\\n\\ud83d\\ude00\"", "{\"a\":1,\"a\":2}", "18446744073709551616", // NOLINT(modernize-raw-string-literal)
                    "-9223372036854775809", "123456789012345678901234567890", "1e400", "-1e400", "1.7976931348623157e308"
                })
        {
            check_same(text);
        }

        // the midpoint between the largest double and 2^1024 rounds to
        // infinity (an overflow), one less to the largest double: with more
        // than 19 digits, Eisel-Lemire cannot decide these, and the overflow
        // check needs the exact comparison with the midpoint
        const std::string midpoint = "179769313486231580793728971405303415079934132710037826936173778980444968292764750946649017977587207096330286416692887910946555547851940402630657488671505820681908902000708383676273854845817711531764475730270069855571366959622842914819860834936475292719074168444365510704342711559699508093042880177904174497792";
        const std::string below = "179769313486231580793728971405303415079934132710037826936173778980444968292764750946649017977587207096330286416692887910946555547851940402630657488671505820681908902000708383676273854845817711531764475730270069855571366959622842914819860834936475292719074168444365510704342711559699508093042880177904174497791";
        check_same(midpoint);
        check_same("-" + midpoint);
        check_same(below);
        check_same("[" + below + "," + midpoint + "]");

        // the check uses the floating-point type of the document: with float,
        // the view rejects what parse() rejects (out_of_range.406), and a
        // double document is not affected
        using float_json = nlohmann::basic_json<std::map, std::vector, std::string, bool, std::int64_t, std::uint64_t, float>;
        CHECK_FALSE(float_json::accept("1e39"));
        CHECK(float_json::accept("3.4028235e38"));
        CHECK_FALSE(float_json::accept("3.4028236e38"));
        for (const char* text :
                {
                    "1e39", "-1e39", "3.4028235e38", "-3.4028235e38", "3.4028236e38", "-3.4028236e38", "3.4028234663852886e38", "1e38",
                    "340282356779733661637539395458142568448", "340282356779733661637539395458142568447.99", "0.00034028236e42",
                    "[1.5e38, 3.5e38]", R"({"a": 1e-50, "b": 1e39})"
                })
        {
            CAPTURE(text)
            const bool float_accepted = float_json::accept(text);
            for (const bool sentinel :
                    {
                        true, false
                    })
            {
                const built f = build<float>(text, false, false, sentinel);
                CHECK(f.ok == float_accepted);
                if (!f.ok)
                {
                    CHECK(f.failure.code == nlohmann::detail::view::error_code::number_overflow);
                }
                CHECK(build<double>(text, false, false, sentinel).ok == json::accept(text));
            }
        }
    }

    SECTION("malformed input")
    {
        for (const char* text :
                {
                    "", " ", "[", "]", "{", "}", "[1,]", "{\"a\":1,}", "[1 2]", "{\"a\" 1}", "{1:2}", "tru", "nul", "fals", "truex", "-", "01", "1.", ".5", "1e", "1e+",
                    "\"", "\"abc", "\"\\x\"", "\"\\u12\"", "\"\\u12G4\"", "\"\\ud800\"", "\"\\udc00\"", "\"\\ud800\\u0041\"", "\"\x01\"", "\"\xff\"", "\"\xc3\"", // NOLINT(modernize-raw-string-literal)
                    "\"\xe0\x80\x80\"", "\"\xed\xa0\x80\"", "[1]x", "[1] [2]", "/", "/*", "/* */ 1", "// c\n1", "1 // c", "[1,/*c*/2]", "[1,2,]"
                })
        {
            check_same(text);
        }
    }

    SECTION("NUL, BOM, and whitespace")
    {
        // a NUL inside a string is a control character, as for json::parse
        // (where a NUL ends the input, it does so only between values)
        for (const bool sentinel :
                {
                    true, false
                })
        {
            const built b = build(std::string("[\"ab\0cd\"]", 9), false, false, sentinel);
            CHECK(!b.ok);
            CHECK(b.failure.code == nlohmann::detail::view::error_code::string_control_character);
            CHECK(b.failure.offset == 4);
        }
        check_same(std::string("[1]\0garbage", 11));
        check_same(std::string("[1\0]", 4));
        check_same(std::string("[1, // c\0\n2]", 12));
        check_same(std::string("[1, /* c\0 */ 2]", 15));
        check_same("\xEF\xBB\xBF[1]");
        check_same("\xEF\xBB[1]");
        check_same(" \t\r\n 7 \n");
        for (const char* text :
                {"[1]\r", "[1]\n", "[1]\r\n", "[1,\r2]", "[1,\r\n2]", "7\r", "\"x\"\r", "{\"a\":\r\n1}\r", "[\n  1,\n  2\n]", "{\n    \"a\": [\n        1\n    ]\n}"
                })
        {
            check_same(text);
        }
    }

    SECTION("deep nesting")
    {
        // the deepest nesting is recorded (materialize() sizes its stack from it)
        CHECK(build("1", false, false, false).data->max_depth == 0);
        CHECK(build("[]", false, false, false).data->max_depth == 1);
        CHECK(build(R"([[1],{"a":[[]]},[]])", false, false, false).data->max_depth == 4);
        // a stack that turns out too small still grows
        const std::string nested = R"([[1],{"a":[[{"b":[]}]]},[]])";
        const built shallow = build(nested, false, false, false);
        REQUIRE(shallow.ok);
        shallow.data->max_depth = 1;
        CHECK(nlohmann::detail::view::materialize<json, false>(*shallow.data, shallow.data->nodes) == json::parse(nested));

        // the open containers beyond 64 levels live on the heap
        for (const std::size_t depth :
                {
                    63u, 64u, 65u, 1000u, 100000u
                })
        {
            const std::string arrays = std::string(depth, '[') + std::string(depth, ']');
            const built b = build(arrays, false, false, false);
            REQUIRE(b.ok);
            CHECK(b.data->node_count == depth);
            CHECK(b.data->nodes[0].next == depth);
            CHECK(b.data->max_depth == depth);
            std::string objects;
            for (std::size_t i = 0; i < depth; ++i)
            {
                objects += "{\"a\":";
            }
            objects += '1' + std::string(depth, '}');
            const built o = build(objects, false, false, false);
            REQUIRE(o.ok);
            CHECK(o.data->node_count == (2 * depth) + 1);
            CHECK(o.data->max_depth == depth);
            CHECK(!build(std::string(depth, '[') + std::string(depth - 1, ']'), false, false, false).ok);
        }
    }

    SECTION("generated documents and damaged copies")
    {
        generator g;
        for (int i = 0; i < 3000; ++i)
        {
            std::string text;
            g.value(text, 0);
            check_same(text);
            // damage: flip one byte, or cut the text
            std::string damaged = text;
            const auto at = static_cast<std::size_t>(g.r(static_cast<int>(damaged.size())));
            static const char replacements[] = {'x', '"', '\\', ',', ':', ']', '}', '[', '{', '1', '-', '.', 'e', '\0', '\n', '/'}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
            damaged[at] = replacements[g.r(16)];
            check_same(damaged);
            check_same(text.substr(0, at));
        }
    }

    SECTION("accept() without an index")
    {
        for (const char* text :
                {
                    "", " ", "\n", "null", "nul", "true", "[", "]", "[]", "{}", "[1,2,3]", "[1,2,3", "[1,2,3,]", "{\"a\":1,}", "{\"a\"}", "{\"a\":}",
                    "[1] x", "[1][2]", "\xEF\xBB\xBF[1]", "[\"a\\", R"(["\u12"])", R"(["\ud800"])", "[\"\x01\"]", "[\"\xff\"]", "[01]", "[1.]",
                    "[.5]", "[-]", "[1e]", "// c\n[1]", "/* c */ {\"a\" /* x */ : 1}", "/* c", "[1] // c", "1e400", "-1e400", "123456789012345678901234567890",
                    R"({"a":1,"a":2})", "[[[]]]", R"("\u00e4\n\ud83d\ude00")"
                })
        {
            check_accept(text);
        }
        // a null byte inside the text, and after it
        check_accept(std::string("[1,\0]", 5));
        check_accept(std::string("[1]\0", 4));
        check_accept(std::string("\0", 1));

        // generated documents and damaged copies, as for the builder above
        generator g;
        for (int i = 0; i < 2000; ++i)
        {
            std::string text;
            g.value(text, 0);
            check_accept(text);
            std::string damaged = text;
            const auto at = static_cast<std::size_t>(g.r(static_cast<int>(damaged.size())));
            static const char replacements[] = {'x', '"', '\\', ',', ':', ']', '}', '[', '{', '1', '-', '.', 'e', '\0', '\n', '/'}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
            damaged[at] = replacements[g.r(16)];
            check_accept(damaged);
            check_accept(text.substr(0, at));
        }

        // nesting beyond the 64 levels that are kept on the builder's own stack, closed and not closed
        for (const std::size_t depth :
                {
                    63u, 64u, 65u, 66u, 200u, 1000u
                })
        {
            check_accept(std::string(depth, '[') + std::string(depth, ']'));
            check_accept(std::string(depth, '[') + std::string(depth - 1, ']'));
            std::string objects;
            for (std::size_t i = 0; i < depth; ++i)
            {
                objects += "{\"k\":";
            }
            objects += "1" + std::string(depth, '}');
            check_accept(objects);
            check_accept(objects.substr(0, objects.size() - 1));
        }

        // objects with enough members to get a hash index when they are indexed (and duplicate keys)
        std::string large = "{";
        for (int i = 0; i < 300; ++i)
        {
            large += (i == 0 ? "\"k" : ",\"k") + std::to_string(i % 200) + "\":" + std::to_string(i);
        }
        check_accept(large + "}");
        check_accept(large);
        check_accept("[" + large + "},{" + large.substr(1) + "}]");

        // the overflow check uses the floating-point type of the document
        using float_json = nlohmann::basic_json<std::map, std::vector, std::string, bool, std::int64_t, std::uint64_t, float>;
        for (const char* text :
                {
                    "1e39", "-1e39", "3.4028235e38", "3.4028236e38", "[1.5e38, 3.5e38]", R"({"a": 1e-50, "b": 1e39})", "340282356779733661637539395458142568448"
                })
        {
            CAPTURE(text)
            CHECK(nlohmann::basic_json_document<float_json>::accept(text) == float_json::accept(text));
        }

        // strings are checked and not decoded: runs of text of every length from 0 to 40 between valid and invalid
        // escapes, UTF-8 sequences and control characters, in values and in keys, cut near the end of the text
        const std::array<const char*, 9> valid = {{"\\n", "\\\"", "\\\\", "\\/", "\\t", "\\u00e4", "\\u20ac", "\\ud83d\\ude00", "\\u0000"}};
        const std::array<const char*, 12> invalid = {{"\\x", "\\ud800", "\\udc00", "\\u12G4", "\\u12", "\\ud83dx", "\\ud83d\\u0041", "\\ud83d\\ud83d", "\\", "\x01", "\x1f", "\x7f"}};
        const std::array<const char*, 6> utf8 = {{"\xc3\xa4", "\xe2\x82\xac", "\xf0\x9f\x98\x80", "\xc3", "\xff", "\x80"}};
        std::mt19937 rng(2029); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
        for (std::size_t run = 0; run <= 40; ++run)
        {
            for (int i = 0; i < 30; ++i)
            {
                std::string content = std::string(rng() % 20, 'a');
                const auto pieces = 1 + (rng() % 6);
                for (unsigned k = 0; k < pieces; ++k)
                {
                    content += valid[rng() % valid.size()];
                    content += std::string(k == 0 ? run : rng() % 41, static_cast<char>('b' + (rng() % 20)));
                    switch (rng() % 8)
                    {
                        case 0:
                            content += utf8[rng() % 3];
                            break;
                        case 1:
                            content += utf8[rng() % utf8.size()];
                            break;
                        case 2:
                            content += invalid[rng() % invalid.size()];
                            break;
                        default:
                            break;
                    }
                }
                for (const std::string& text :
                        {
                            "[\"" + content + "\"]", "{\"" + content + "\":1}", "[\"" + content, "[\"" + content.substr(0, content.size() - (rng() % 4)) + "\"]"
                        })
                {
                    check_accept(text);
                }
            }
        }
    }

    SECTION("escapes in a row")
    {
        for (const char* content :
                {
                    "\\n", R"(\n\t\\)", R"(\u00e9\u00e9\u4e2d)", "\\u00e9\\u00e", "\\u00e9\\", "\\n\\q", R"(\n\ud83d\ude00\n)",
                    R"(\ud83d\ude00\ud83d)", R"(\n\n\n abc \n\n)", "\\n\x01", "\\n\xC3\x28", "\\n\\"
                })
        {
            check_accept(std::string("[\"") + content + "\"]");
            check_accept(std::string("[\"") + content);
            check_accept(std::string("{\"") + content + "\":1}");
        }
    }

    SECTION("test files")
    {
        for (const char* name :
                {
                    "/json.org/1.json", "/json.org/2.json", "/json.org/3.json", "/json.org/4.json", "/json.org/5.json",
                    "/json_testsuite/sample.json", "/nativejson-benchmark/canada.json", "/nativejson-benchmark/citm_catalog.json",
                    "/nativejson-benchmark/twitter.json", "/json_tests/pass1.json", "/json_tests/pass2.json", "/json_tests/pass3.json"
                })
        {
            CAPTURE(name)
            const std::ifstream f(std::string(TEST_DATA_DIRECTORY) + name, std::ios::binary);
            std::stringstream ss;
            ss << f.rdbuf();
            const std::string text = ss.str();
            REQUIRE(!text.empty());
            const built b = build(text, false, false, true);
            REQUIRE(b.ok);
            CHECK(value_of(b) == json::parse(text));
        }
    }
}

TEST_CASE("json_view builder: strings across vector blocks")
{
    // Strings are scanned 8 or 16 bytes at a time (NEON, SSE2, or SWAR) and
    // non-ASCII text with the vector UTF-8 check (NEON, SSSE3) or one sequence
    // at a time. Sequences are placed so that they start at every offset
    // around the block boundaries of keys (16, 32) and values (8, 24), with
    // text of several lengths after them.
    const std::array<std::size_t, 16> prefixes = {{0, 6, 7, 8, 13, 14, 15, 16, 21, 22, 23, 24, 29, 30, 31, 32}};
    const std::array<std::size_t, 3> suffixes = {{0, 3, 17}};
    const auto around = [&](const std::string & seq, std::size_t prefix, std::size_t suffix)
    {
        return std::string(prefix, 'a') + seq + std::string(suffix, 'b');
    };

    SECTION("every two-byte sequence")
    {
        for (unsigned lead = 0x80; lead <= 0xFF; ++lead)
        {
            for (unsigned second = 0; second <= 0xFF; ++second)
            {
                if (second == '"' || second == '\\')
                {
                    continue;
                }
                const std::string seq = {static_cast<char>(lead), static_cast<char>(second)};
                check_string(around(seq, prefixes[(lead + second) % 16], suffixes[second % 3]));
            }
        }
    }

    SECTION("three- and four-byte sequences")
    {
        const std::array<unsigned, 8> conts = {{0x7F, 0x80, 0x8F, 0x90, 0x9F, 0xA0, 0xBF, 0xC0}};
        for (unsigned lead = 0xE0; lead <= 0xF7; ++lead)
        {
            for (const unsigned b2 : conts)
            {
                for (const unsigned b3 : conts)
                {
                    for (const std::size_t prefix : prefixes)
                    {
                        std::string seq = {static_cast<char>(lead), static_cast<char>(b2), static_cast<char>(b3)};
                        if (lead >= 0xF0)
                        {
                            seq += static_cast<char>(prefix % 2 == 0 ? 0x80 : 0xBF);
                        }
                        check_string(around(seq, prefix, suffixes[prefix % 3]));
                        // cut short before the end of the string
                        check_string(around(seq.substr(0, seq.size() - 1), prefix, suffixes[prefix % 3]));
                    }
                }
            }
        }
    }

    SECTION("long runs of text with one damaged byte")
    {
        const std::array<const char*, 7> chars = {{"a", "\xc3\xa9", "\xe3\x81\x82", "\xf0\x9f\x98\x80", "\xed\x9f\xbf", "\xef\xbf\xbf", "\xf4\x8f\xbf\xbf"}};
        const std::array<char, 11> damage = {{'\x80', '\xbf', '\xc0', '\xc1', '\xe0', '\xed', '\xf5', '\xff', '\x1f', '"', '\\'}};
        std::mt19937 rng(5295); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
        for (int i = 0; i < 4000; ++i)
        {
            std::string text;
            const auto n = rng() % 60;
            for (unsigned k = 0; k < n; ++k)
            {
                text += chars[rng() % chars.size()];
            }
            check_string(text);
            if (!text.empty())
            {
                text[rng() % text.size()] = damage[rng() % damage.size()];
                check_string(text);
            }
        }
    }
}

TEST_CASE("json_view builder: fraction digits")
{
    // The digits of a fraction are skipped 16 bytes at a time where there are
    // that many left (SSE2), and one at a time after that. Fractions of every
    // length from 0 to 40 digits, followed by every kind of byte that ends a
    // number or lies next to the digits in ASCII ('/' and ':'), as values, as
    // keys' neighbours, and at the very end of the text (a vector without a
    // terminating NUL). The length of the number is part of the value that
    // the test compares with json::parse().
    const std::string followers = ",]}/:.eE+-x \n\t\"09";
    std::mt19937 rng(2028); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
    for (std::size_t digits = 0; digits <= 40; ++digits)
    {
        for (int i = 0; i < 3; ++i)
        {
            std::string fraction;
            for (std::size_t k = 0; k < digits; ++k)
            {
                fraction += static_cast<char>('0' + (rng() % 10));
            }
            const std::string number = std::string(rng() % 2 == 0 ? "-" : "") + std::to_string(rng() % 100000) + "." + fraction;
            check_same(number);
            check_same("[" + number + "]");
            std::string pair;
            pair.reserve((number.size() * 2) + 3);
            pair += '[';
            pair += number;
            pair += ',';
            pair += number;
            pair += ']';
            check_same(pair);
            check_same("{\"a\":" + number + "}");
            for (const char follower : followers)
            {
                check_same(number + follower);
                check_same("[" + number + follower + "]");
                check_same("[" + number + follower + std::string(rng() % 20, '1'));
            }
            // everything near the end of the text: the number cut in every place
            for (std::size_t cut = 1; cut <= 18 && cut <= number.size(); ++cut)
            {
                check_same(number.substr(0, number.size() - cut));
                check_same("[" + number.substr(0, number.size() - cut));
            }
        }
    }
}

TEST_CASE("json_view builder: escapes between runs of text")
{
    // The text between escapes is copied 16 bytes at a time where there are
    // that many bytes left, and with the UTF-8 check where there is
    // non-ASCII text. Runs of every length from 0 to 40 between valid and
    // invalid escapes, UTF-8 sequences, and control characters, in strings
    // that are cut at all places near the end of the text.
    const std::array<const char*, 9> valid = {{"\\n", "\\\"", "\\\\", "\\/", "\\t", "\\u00e4", "\\u20ac", "\\ud83d\\ude00", "\\u0000"}};
    const std::array<const char*, 9> invalid = {{"\\x", "\\ud800", "\\udc00", "\\u12G4", "\\u12", "\\ud83dx", "\\ud83d\\u0041", "\\", "\x01"}};
    const std::array<const char*, 6> utf8 = {{"\xc3\xa4", "\xe2\x82\xac", "\xf0\x9f\x98\x80", "\xc3", "\xff", "\x80"}};
    std::mt19937 rng(2026); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
    for (std::size_t run = 0; run <= 40; ++run)
    {
        for (int i = 0; i < 60; ++i)
        {
            std::string content = std::string(rng() % 20, 'a');
            const auto pieces = 1 + (rng() % 6);
            for (unsigned k = 0; k < pieces; ++k)
            {
                content += valid[rng() % valid.size()];
                content += std::string(k == 0 ? run : rng() % 41, static_cast<char>('b' + (rng() % 20)));
                switch (rng() % 8)
                {
                    case 0:
                        content += utf8[rng() % 3];
                        break;
                    case 1:
                        content += utf8[rng() % utf8.size()];
                        break;
                    case 2:
                        content += invalid[rng() % invalid.size()];
                        break;
                    default:
                        break;
                }
            }
            check_string(content);
            check_string(content.substr(0, content.size() - (rng() % 4)));
        }
    }
    // the text before the first escape, and runs and escapes at the end of the text
    for (std::size_t before = 0; before <= 40; ++before)
    {
        for (const char* escape : valid)
        {
            check_string(std::string(before, 'a') + escape);
            check_string(std::string(before, 'a') + escape + std::string(before % 19, 'z'));
            check_string(std::string(before, 'a') + escape + escape + std::string(before % 19, 'z'));
        }
    }
}

TEST_CASE("json_view builder: chains of unicode escapes")
{
    // Consecutive \uXXXX escapes are decoded in a loop of their own. Chains of
    // every length from 1 to 40 of escapes that give one, two, and three
    // bytes of UTF-8, in upper and lower case, followed by what ends a chain:
    // the end of the string, text, another escape, UTF-8, and everything that
    // is not a valid escape (a bad digit at every position of the last
    // escape, a lone surrogate, a surrogate pair, a cut in every place).
    const std::array<const char*, 8> chain = {{"\\u0041", "\\u00e4", "\\u00E4", "\\u20ac", "\\u3042", "\\uFFFF", "\\u0000", "\\u07ff"}};
    const std::array<const char*, 12> ends = {{"", "abc", "\\n", "\\u00e9", "\\ud83d\\ude00", "\\ud83d", "\\ude00", "\\ud83d\\u0041", "\\u12G4", "\\u12", "\xc3\xa4", "\\"}};
    std::mt19937 rng(2027); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
    for (std::size_t length = 1; length <= 40; ++length)
    {
        for (int i = 0; i < 20; ++i)
        {
            std::string content = std::string(rng() % 20, 'a');
            for (std::size_t k = 0; k < length; ++k)
            {
                content += chain[rng() % chain.size()];
            }
            const std::string whole = content;
            for (const char* end : ends)
            {
                check_string(whole + end);
                check_string(whole + end + std::string(rng() % 19, 'z'));
            }
            // a bad digit at every position of every escape near the end of the chain
            for (std::size_t back = 1; back <= 6 && back <= length; ++back)
            {
                for (std::size_t digit = 2; digit < 6; ++digit)
                {
                    std::string broken = whole;
                    broken[broken.size() - (6 * back) + digit] = "gG\"\x01 z"[rng() % 6];
                    check_string(broken);
                }
            }
            // the text cut in every place of the last three escapes
            for (std::size_t cut = 0; cut <= 18 && cut <= whole.size(); ++cut)
            {
                check_string(whole.substr(0, whole.size() - cut));
            }
        }
    }
    // a chain longer than the first growth of the arena, in a key and in a value
    std::string long_chain;
    for (int i = 0; i < 3000; ++i)
    {
        long_chain += chain[static_cast<std::size_t>(i) % chain.size()];
    }
    check_string(long_chain);
    check_string(long_chain + "\\ud83d\\ude00" + long_chain);
}

TEST_CASE("json_view node integer bits")
{
    using nlohmann::detail::view::integer_bits;
    using nlohmann::detail::view::set_integer_bits;

    // an integer lives in len (low half) and next (high half), on any byte
    // order; a big-endian target must not store the native word over both
    SECTION("set_integer_bits and integer_bits")
    {
        node n = {};
        for (const std::uint64_t v :
                {
                    std::uint64_t{0}, std::uint64_t{1}, std::uint64_t{0xFFFFFFFFu}, std::uint64_t{0x100000000u},
                    std::uint64_t{0x0000000200000003u}, std::uint64_t{0x0123456789ABCDEFu}, std::uint64_t{0xFFFFFFFFFFFFFFFEu}
                })
        {
            CAPTURE(v)
            n.kind = nlohmann::detail::view::node_kind::link;
            n.flags = 0xA5;
            n.extra = 0x1234;
            n.off = 0x89ABCDEFu;
            set_integer_bits(n, v);
            CHECK(integer_bits(n) == v);
            CHECK(n.len == static_cast<std::uint32_t>(v));
            CHECK(n.next == static_cast<std::uint32_t>(v >> 32));
            // the other fields are untouched
            CHECK(n.kind == nlohmann::detail::view::node_kind::link);
            CHECK(n.flags == 0xA5);
            CHECK(n.extra == 0x1234);
            CHECK(n.off == 0x89ABCDEFu);
        }
    }

    SECTION("parsed integers")
    {
        struct integer_case
        {
            const char* text;
            std::uint64_t bits;
        };
        for (const integer_case c :
                {
                    integer_case{"[8589934595]", 0x0000000200000003u}, integer_case{"[4294967296]", 0x100000000u}, integer_case{"[4294967295]", 0xFFFFFFFFu},
                    integer_case{"[-2]", 0xFFFFFFFFFFFFFFFEu}, integer_case{"[-4294967297]", 0xFFFFFFFEFFFFFFFFu}, integer_case{"[18446744073709551615]", 0xFFFFFFFFFFFFFFFFu},
                    integer_case{"[7]", 7u}
                })
        {
            CAPTURE(c.text)
            const built b = build(c.text, false, false, true);
            REQUIRE(b.ok);
            const node& n = b.data->nodes[1];
            CHECK(integer_bits(n) == c.bits);
            CHECK(n.len == static_cast<std::uint32_t>(c.bits));
            CHECK(n.next == static_cast<std::uint32_t>(c.bits >> 32));
        }
    }
}

TEST_CASE("json_view node array size limit")
{
    // a node array larger than the address space is refused, not wrapped to a
    // small allocation (the size computation overflows on 32-bit targets, and
    // for absurd counts everywhere)
    std::unique_ptr<document_data, document_data::deleter> d(document_data::create(0));
    d->reserve(8);
    REQUIRE(d->node_capacity >= 8);
    d->node_count = 2;
    const std::size_t cap = d->node_capacity;
    node* const nodes = d->nodes;

#if !defined(JSON_NOEXCEPTION)
    const std::size_t too_many = document_data::max_nodes() + 1;
    CHECK_THROWS_AS(d->reserve(too_many), std::bad_alloc&);
    CHECK_THROWS_AS(d->reserve((std::numeric_limits<std::size_t>::max)()), std::bad_alloc&);
    // the array is unchanged
    CHECK(d->nodes == nodes);
    CHECK(d->node_capacity == cap);
    CHECK(d->node_count == 2);
#endif

    // the largest count that fits is not refused by the check (nothing is
    // allocated for a count that is already there)
    d->reserve(cap);
    CHECK(d->nodes == nodes);
}

TEST_CASE("json_view document_data::holds() (the debug check of read())")
{
    std::unique_ptr<document_data, document_data::deleter> d(document_data::create(0));
    const std::string other = "[1,2,3]";
    // an empty document holds nothing
    CHECK(!d->holds(other.data(), other.size()));

    SECTION("owned text")
    {
        d->owned = R"({"a":"some text that does not fit a short string"})";
        const char* const b = d->owned.data();
        CHECK(d->holds(b, 1));
        CHECK(d->holds(b + 5, 3));
        CHECK(d->holds(b + d->owned.size() - 1, 1));
        // also after clear(), which keeps the buffer that the next parse writes
        d->owned.clear();
        // (b is only compared with the buffer, never read)
        CHECK(d->holds(b, 4)); // NOLINT(clang-analyzer-cplusplus.InnerPointer)
        CHECK(!d->holds(other.data(), other.size()));
        CHECK(!d->holds(b, 0));
    }

    SECTION("decoded strings")
    {
        d->arena.assign(32, 'x');
        CHECK(d->holds(d->arena.data() + 31, 1));
        CHECK(d->holds(d->arena.data() + 31, 8)); // (overlapping the end)
        CHECK(!d->holds(other.data(), other.size()));
    }

    SECTION("owned image")
    {
        d->owned_image.assign(16, 0);
        CHECK(d->holds(reinterpret_cast<const char*>(d->owned_image.data()) + 8, 2)); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
    }

    SECTION("current edit buffer")
    {
        d->edits.reset(new document_data::edit_state()); // NOLINT(cppcoreguidelines-owning-memory)
        CHECK(!d->holds(other.data(), other.size()));
        d->edits->texts.emplace_back(new char[16]); // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays,cppcoreguidelines-owning-memory)
        d->edits->text_cap = 16;
        CHECK(d->holds(d->edits->texts.back().get() + 3, 3));
        CHECK(!d->holds(other.data(), other.size()));
    }
}

TEST_CASE("json_view read() of inputs the check must accept")
{
    // in a debug build each read() below runs the check; none of the inputs
    // is held by the document
    const std::string text = R"({"a":"x\ny","b":[1,2]})";
    nlohmann::json_document d;
    d.read(text); // borrowed
    d.read(text); // the same borrowed text again
    CHECK(d.root()["b"][1].get<int>() == 2);
    const std::string copy(d.root()["a"].get_string()); // a decoded string, copied first
    d.read(std::string(text)); // owned
    d.read(R"(["x"])");
    d.read(text);
    CHECK(copy == "x\ny");
    nlohmann::json_editable_document e;
    e.read(text);
    e.set(e.root(), "a", "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]");
    const std::string edited(e.root()["a"].get_string()); // an edited string, copied first
    e.read(edited);
    CHECK(e.root().size() == 16);
}