Make unflatten() linear in the length of the keys

unflatten() decides in a first pass which prefixes of the keys denote arrays
(those that have a reference token 0 among their children), and looks up
prefixes again in the second pass. A prefix was identified by hashing it, and
by comparing it byte by byte with the entry in the set, from its beginning.
A key with n tokens therefore cost n^2/2 bytes: 100,000 tokens "/0" took
2.4 s (3.12.0: 5 ms), and so did "/0" followed by "/1" tokens, because every
new level looks its prefix up. Keys in the order of an unsorted object type
(ordered_json) defeated the shortcut for keys that share a beginning with the
previous one: four keys were enough to be quadratic.

Prefixes of less than 64 bytes are kept in a hash table and compared as
before, which costs a bounded number of bytes. Longer prefixes are kept in a
tree whose nodes are looked up by their parent and the text of one token. The
node of a prefix is found by walking the tokens of the key from the root, so
all prefixes of a key together cost one pass over the key, and no prefix is
compared as a whole. The nodes along the key walked last are kept, so keys
that share a beginning do not walk it again. The array/object decision and
the independence from the order of the keys are unchanged.

The hash function is seeded with a value derived from the address of a local
variable, which address space layout randomization changes between
processes, so keys cannot be crafted to collide in advance: with the fixed
constants, 20,000 keys of 16 + 2 bytes with the same hash took 0.5 s (random
keys, and 3.12.0: 7 ms). Where addresses are not randomized, or when the seed
is known, k short prefixes can still collide and cost k^2 / 2 comparisons of
fewer than 64 bytes. Results do not depend on the seed.

Measurements (Apple clang -O2, arm64), unflatten() of one key with n tokens:

  tokens "/0"          n=25k  n=50k  n=100k  n=200k
  before              175 ms 617 ms 2437 ms 9729 ms
  after                 4 ms   6 ms   12 ms   27 ms
  3.12.0                1 ms   3 ms    5 ms   10 ms

  "/0" then "/1"       n=25k  n=50k  n=100k  n=200k
  before              153 ms 603 ms 2436 ms 9678 ms
  after                 1 ms   3 ms    5 ms   10 ms
  3.12.0                1 ms   3 ms    5 ms   11 ms

  ordered_json, 4 keys /0*m/a0, /10, /0*m/a1, /11
                       m=25k  m=50k  m=100k  m=200k
  before              397 ms 1402 ms 5191 ms 20723 ms
  after                 4 ms   7 ms   15 ms   33 ms
  3.12.0                2 ms   3 ms    8 ms   17 ms

Ordinary documents (flatten() then unflatten(), instructions retired): within
0.3 % of before for canada, citm_catalog, twitter, jeopardy, mesh,
update-center and random from the benchmark corpus.

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

docs/mkdocs/docs/api/basic_json/from_ubjson.md

@@ -89,10 +89,8 @@ Strong guarantee: if an exception is thrown, there are no changes in the JSON va
 - Throws [out_of_range.406](../../home/exceptions.md#jsonexceptionout_of_range406) if a high-precision number, or a
   float64 when `number_float_t` is `float`, does not fit into `number_float_t`
 - Throws [out_of_range.408](../../home/exceptions.md#jsonexceptionout_of_range408) if the count of an optimized
-  container exceeds the capacity of the container (or of `std::size_t`; an array of type `N` is empty, so only the
-  latter applies to it), if an optimized array of `Z`, `T`, or `F` has more than 1,048,576 elements, or if the
-  optimized arrays of `Z`, `T`, and `F` in the input together have more than 1,048,576 elements plus 4 for every byte
-  read so far
+  container exceeds the capacity of the container (or of `std::size_t`), or if an optimized array of `Z`, `T`, or `F` has
+  more than 1,048,576 elements
 
 ## Complexity
 
@@ -134,9 +132,6 @@ Linear in the size of the input.
 - Extended container support (1) to include types with lvalue-only ADL `begin`/`end` (matching `std::begin`/`std::end` semantics) in version 3.13.0.
 - Extended overload (2) to accept heterogeneous iterator+sentinel pairs (C++20 ranges support) in version 3.13.0.
 - Added `error_handler` parameter in version 3.13.0.
-- Report `start_array(0)` to a SAX handler for an optimized array of type `N` (`[$N#n`), whatever its count, in version
-  3.13.0.
-- Limited the total number of elements of optimized arrays of `Z`, `T`, and `F` in one input in version 3.13.0.
 
 !!! warning "Deprecation"
 

docs/mkdocs/docs/api/basic_json/to_ubjson.md

@@ -117,8 +117,5 @@ Linear in the size of the JSON value `j`.
 - Added `error_handler` parameter in version 3.13.0. Its default, `keep`, writes the bytes of a string or object key
   that is not valid UTF-8 unchanged, as before; `strict` (the default if
   [`JSON_STRICT_BINARY_UTF8`](../macros/json_strict_binary_utf8.md) is enabled) throws `type_error.316`.
-- Writes arrays of `Z`, `T`, or `F` without the `$` type annotation (`[#n Z Z ...`) once their elements in one call
-  add up to more than 1,048,576, in version 3.13.0, so that `from_ubjson` can read the output back. Such output is
-  larger: 270,000 rows of 100 `null` values take 26.8 MB instead of 1.35 MB.
 - Throws `type_error.321` for a discarded value since version 3.13.0; previously, a discarded value nested in an
   array or object was silently skipped, producing invalid UBJSON.

docs/mkdocs/docs/features/binary_formats/ubjson.md

@@ -122,18 +122,9 @@ The library uses the following mapping from JSON values types to UBJSON types ac
     already is the value. Its declared count is therefore the only thing that decides how much memory the receiving side
     allocates, and a handful of bytes can describe billions of elements. `from_ubjson` rejects such an array with
     [`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408) when the count exceeds 1,048,576
-    (`1 << 20`), or when the counts of all such arrays in the input add up to more than 1,048,576 plus 4 for every byte
-    read so far. `to_ubjson` therefore writes an array of these types in the counted but untyped form when it is longer
-    than that, or when it would bring the total of the typed arrays written so far above 1,048,576: the `$` type marker
-    is dropped, the `#` count is kept, and every element is written with its own marker (`[#l 1048577 Z Z ...`), so
-    everything it produces can be read back. Only input from another encoder, or written by version 3.12.0 and earlier of
-    this library, can exceed the limit: for example, 1,100 rows of 1,000 `null` values or 210,000 rows of 25, each with
-    a `$Z` annotation. Version 3.12.0 writes such a row in 5 bytes (6 above 255 elements), so rows of 20 or fewer such
-    values are never rejected. Objects and untyped counted arrays are not subject to this limit.
-
-    An optimized array of type `N` (no-op) is empty whatever its count is, because a no-op is not a value. Its count is
-    not passed on: `sax_parse` reports `start_array(0)` (versions before 3.13.0 reported the declared count), and the DOM
-    parser reserves nothing for it.
+    (`1 << 20`), and `to_ubjson` writes longer arrays of these types in the counted but untyped form: the `$` type marker is
+    dropped, the `#` count is kept, and every element is written with its own marker (`[#l 1048577 Z Z ...`), so any value
+    it produces can be read back. Objects and untyped counted arrays are not subject to this limit.
 
 !!! info "Binary values"
 
@@ -189,11 +180,10 @@ The library maps UBJSON types to JSON value types as follows:
 
     Every well-formed UBJSON value can be converted to a JSON value, with these exceptions: a high-precision number
     outside the range of `number_float_t` ([`out_of_range.406`](../../home/exceptions.md#jsonexceptionout_of_range406)),
-    optimized arrays of `Z`, `T`, or `F` with more elements than the limit allows (1,048,576 plus 4 per byte read),
-    and a count that exceeds the capacity of the container
-    ([`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408)). High-precision numbers that do not
-    fit an integer type are stored as floating-point numbers and may lose precision. Ill-formed input is rejected with a
-    parse error.
+    an optimized array of `Z`, `T`, or `F` with more than 1,048,576 elements, and a count that exceeds the capacity of the
+    container ([`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408)). High-precision numbers that
+    do not fit an integer type are stored as floating-point numbers and may lose precision. Ill-formed input is rejected
+    with a parse error.
 
 !!! info "Duplicate object keys"
 

docs/mkdocs/docs/features/parsing/untrusted_input.md

@@ -72,22 +72,10 @@ For the binary formats, an announced size is never trusted outright:
   (reported as a parse error) instead of triggering an oversized allocation.
 - When an array announces its number of elements and the array container supports `reserve()` (as `#!cpp std::vector`,
   the default, does), the library reserves storage for at most 16384 of them upfront, regardless of how large the
-  announced count is; further elements still grow the container normally as they are read. A count that no
-  input backs, as in a truncated input, reserves at most that much until the parse error is reported. A parse that
-  completes keeps storage for such a count only where the elements take no input at all, which the two
-  [UBJSON](../binary_formats/ubjson.md) cases below cover.
+  announced count is; further elements still grow the container normally as they are read.
 - An announced array or object size that exceeds what the target container could ever hold (its `max_size()`) is
   rejected immediately as [`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408), without
   attempting to allocate anything.
-- A [UBJSON](../binary_formats/ubjson.md) array of the no-op type (`[$N#<n>`) is empty whatever count it declares: a
-  SAX handler is told `start_array(0)` and the DOM parser reserves nothing.
-- A UBJSON array of type `Z`, `T` or `F` has no payload, so its announced count is not bounded by the input. One array
-  may announce at most 1,048,576 elements, and all such arrays of one input together may contain at most 1,048,576
-  elements plus 4 for every byte read so far (checked when each array's header has been read); beyond that the input is
-  rejected as [`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408). For a DOM that bounds the memory these
-  arrays can need to about 80 bytes per byte of input plus about 33 MB for the first 1,048,576 elements; a SAX handler
-  receives at most that many events. Every other optimized array element, and every UBJSON object member (it has a
-  key), takes at least one byte of input.
 
 ## Strings
 

docs/mkdocs/docs/home/exceptions.md

@@ -1050,17 +1050,11 @@ The size of an array or object in a [binary format](../features/binary_formats/i
 the size following `#` for [UBJSON](../features/binary_formats/ubjson.md)/[BJData](../features/binary_formats/bjdata.md),
 or the encoded length for [CBOR](../features/binary_formats/cbor.md).
 
-The exception is also thrown for [UBJSON](../features/binary_formats/ubjson.md) arrays of a type that is encoded by
-its marker alone (`Z`, `T` or `F`). Such an array has no payload, so its count alone decides how much memory is
-allocated, and a handful of bytes would otherwise describe billions of values. It is thrown if the declared count of one
-array exceeds 1,048,576 (`1 << 20`), and if the counts of all such arrays read so far in one input add up to more than
-1,048,576 plus 4 for every byte of the input read when the header of the last array has been read.
-[`to_ubjson`](../api/basic_json/to_ubjson.md) writes an array of these types without the `$` type annotation (the `#`
-count and one marker per element are kept) when it is longer, or when it would bring the total of the typed arrays
-written so far above 1,048,576, so everything it produces can be read back. Only input written by another encoder, or
-by version 3.12.0 and earlier of this library, can exceed the limit: for example, 1,100 rows of 1,000 `null` values or
-210,000 rows of 25, each with a `$Z` annotation. Version 3.12.0 writes such a row in 5 bytes (6 above 255 elements),
-so rows of 20 or fewer such values are never rejected.
+The exception is also thrown for a [UBJSON](../features/binary_formats/ubjson.md) array of a type that is encoded by its
+marker alone (`Z`, `T` or `F`) whose declared count exceeds 1,048,576 (`1 << 20`). Such an array has no payload, so its
+count alone decides how much memory is allocated, and a handful of bytes would otherwise describe billions of values.
+[`to_ubjson`](../api/basic_json/to_ubjson.md) writes longer arrays of these types without the `$` type annotation (the `#`
+count and one marker per element are kept), so any value it produces can still be read back.
 
 !!! failure "Example messages"
 
@@ -1076,9 +1070,6 @@ so rows of 20 or fewer such values are never rejected.
     ```
     [json.exception.out_of_range.408] syntax error while parsing UBJSON size: excessive array size
     ```
-    ```
-    [json.exception.out_of_range.408] syntax error while parsing UBJSON size: excessive number of elements without payload
-    ```
 
 ### json.exception.out_of_range.409
 

include/nlohmann/detail/input/binary_reader.hpp

@@ -73,46 +73,13 @@ the input.
 
 This is a sanity bound rather than a security boundary, and it is far above
 any container met in practice. @ref binary_writer falls back to the
-unoptimized encoding for longer containers, and for containers that together
-with the ones before them would exceed @ref valueless_elements_base, so that a
-value serialized by this library can always be read back.
+unoptimized encoding for longer containers, so that a value serialized by
+this library can always be read back.
 
 @sa https://github.com/nlohmann/json/issues/2793
 */
 JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 20;
 
-/*!
-@brief number of elements of valueless UBJSON containers accepted on top of
-       @ref valueless_elements_per_byte
-
-The limit @ref max_valueless_container_size applies to each container on its
-own, so on its own it lets 9 bytes announce 1048576 values, and every further
-9 bytes another 1048576. The elements of all containers of a valueless type
-in one input are therefore added up, and the sum must stay below this base
-plus @ref valueless_elements_per_byte for every byte read so far. The base is
-the per-container limit, so a container that was accepted on its own before
-the sum was introduced is still accepted at the start of an input.
-*/
-JSON_INLINE_VARIABLE constexpr std::size_t valueless_elements_base = max_valueless_container_size;
-
-/*!
-@brief number of elements of valueless UBJSON containers accepted per byte of
-       input, in addition to @ref valueless_elements_base
-
-An element of a value that has a payload costs at least one byte of input.
-Valueless elements are accepted at a rate of 4 per byte. A value takes 16
-bytes of memory in a DOM, so these arrays add about 80 bytes of memory per
-byte of input (measured: 77; one `Z` per byte needs about 32), beyond what the
-same bytes cost anyway, plus the base. This bounds the arrays of valueless
-type, not the memory of a whole document. Containers written by
-@ref binary_writer never need more than the base, because it writes an array
-in the unoptimized form once the typed arrays written so far and this one add
-up to more than that. The rate matters for input written by other encoders and
-by versions before 3.13.0 only; in the data this was measured on, no input has
-more than 0.17 elements per byte.
-*/
-JSON_INLINE_VARIABLE constexpr std::size_t valueless_elements_per_byte = 4;
-
 ///////////////////
 // binary reader //
 ///////////////////
@@ -3733,37 +3700,6 @@ class binary_reader
         return emit_unsigned(number);
     }
 
-    /*!
-    @brief add the elements of a container of a valueless type to the total of
-           the input and check the total against the input read so far
-
-    A container of type 'Z', 'T' or 'F' has no payload, so its elements are the
-    only ones for which the input does not bound the count. The check is made
-    once per container, not per element.
-
-    @param[in] count  number of elements the container declares; at most
-                      @ref max_valueless_container_size
-    @return false if the total is more than @ref valueless_elements_base plus
-            @ref valueless_elements_per_byte for every byte read so far; the
-            total is not changed then
-    */
-    bool charge_valueless_elements(const std::size_t count) noexcept
-    {
-        // the limit saturates instead of overflowing when size_t is 32 bits
-        // wide and a very large input has been read; valueless_elements
-        // never exceeds the limit, so the difference cannot underflow
-        constexpr std::size_t max_size = (std::numeric_limits<std::size_t>::max)();
-        const std::size_t limit = chars_read <= (max_size - valueless_elements_base) / valueless_elements_per_byte
-                                  ? valueless_elements_base + (valueless_elements_per_byte * chars_read)
-                                  : max_size;
-        if (JSON_HEDLEY_UNLIKELY(count > limit - valueless_elements))
-        {
-            return false;
-        }
-        valueless_elements += count;
-        return true;
-    }
-
     /*!
     @return whether array creation completed
     */
@@ -3849,27 +3785,24 @@ class binary_reader
             // declared count alone decides how much is allocated; the check is
             // made before the start event so that no container is opened that
             // is then abandoned. See @ref max_valueless_container_size.
-            if (JSON_HEDLEY_UNLIKELY(size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F'))
+            if (JSON_HEDLEY_UNLIKELY((size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F')
+                                     && size_and_type.first > max_valueless_container_size))
             {
-                if (JSON_HEDLEY_UNLIKELY(size_and_type.first > max_valueless_container_size))
-                {
-                    return out_of_range_error(exception_id::container_too_large, "excessive array size", "size");
-                }
-                if (JSON_HEDLEY_UNLIKELY(!charge_valueless_elements(size_and_type.first)))
-                {
-                    return out_of_range_error(exception_id::container_too_large, "excessive number of elements without payload", "size");
-                }
+                return out_of_range_error(exception_id::container_too_large, "excessive array size", "size");
             }
 
-            // a no-op is not a value, so an array of them is empty whatever
-            // count it declares: the SAX parser is told so, instead of being
-            // made to reserve storage for a count that no input backs
-            const std::size_t announced = size_and_type.second == 'N' ? 0 : size_and_type.first;
-            if (JSON_HEDLEY_UNLIKELY(!enter_array(announced, size_and_type.second)))
+            if (JSON_HEDLEY_UNLIKELY(!enter_array(size_and_type.first, size_and_type.second)))
             {
                 return false;
             }
 
+            if (size_and_type.second == 'N')
+            {
+                // a no-op is not a value, so a container of them holds none;
+                // the declared size has already been passed to the SAX parser
+                container_stack.back().remaining = 0;
+            }
+
             return size_and_type.second == 0
                    || parse_ubjson_typed_run(container_stack.back().remaining, size_and_type.second, std::integral_constant<bool, bulk_scan> {});
         }
@@ -5181,10 +5114,6 @@ class binary_reader
     /// the number of characters read
     std::size_t chars_read = 0;
 
-    /// UBJSON: the sum of the element counts of the containers of a valueless
-    /// type read so far; see @ref charge_valueless_elements
-    std::size_t valueless_elements = 0;
-
     /// whether we can assume little endianness
     const bool is_little_endian = little_endianness();
 

include/nlohmann/detail/json_pointer.hpp

@@ -852,139 +852,6 @@ class json_pointer
     }
 
   private:
-    /*!
-    @brief the pointer prefixes of a flattened object that denote arrays
-
-    @ref unflatten creates arrays exactly below the prefixes that have a
-    reference token 0 among their children, and objects everywhere else.
-    Deciding this up front keeps the result independent of the order in which
-    the flattened object is iterated, which is unspecified for some object
-    types.
-
-    A prefix is identified by the text of the key it is the beginning of:
-    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
-    The set refers to the keys, which must outlive it.
-    */
-    class array_prefix_set
-    {
-      public:
-        void insert(const char* data, std::size_t size)
-        {
-            // flattened objects are usually sorted, so most keys that have a
-            // 0 yield the prefix of the previous one
-            if (last_data != nullptr && last_size == size && std::memcmp(last_data, data, size) == 0)
-            {
-                return;
-            }
-            last_data = data;
-            last_size = size;
-
-            if (table.empty())
-            {
-                table.resize(16);
-            }
-            const std::size_t hash = hash_of(data, size);
-            const std::size_t mask = table.size() - 1;
-            std::size_t i = hash & mask;
-            while (table[i].data != nullptr)
-            {
-                if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
-                {
-                    return;
-                }
-                i = (i + 1) & mask;
-            }
-            table[i] = slot(hash, data, size);
-
-            // keep the load factor below 1/2
-            if (++used * 2 > table.size())
-            {
-                grow();
-            }
-        }
-
-        bool empty() const noexcept
-        {
-            return used == 0;
-        }
-
-        bool contains(const char* data, std::size_t size) const noexcept
-        {
-            if (used == 0)
-            {
-                return false;
-            }
-            const std::size_t hash = hash_of(data, size);
-            const std::size_t mask = table.size() - 1;
-            for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
-            {
-                if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
-                {
-                    return true;
-                }
-            }
-            return false;
-        }
-
-      private:
-        struct slot
-        {
-            slot() noexcept = default;
-
-            slot(std::size_t h, const char* d, std::size_t s) noexcept
-                : hash(h), data(d), size(s)
-            {}
-
-            std::size_t hash = 0;
-            const char* data = nullptr; // nullptr: the slot is empty
-            std::size_t size = 0;
-        };
-
-        static std::size_t hash_of(const char* data, std::size_t size) noexcept
-        {
-            std::uint64_t h = 0x9E3779B97F4A7C15ULL ^ size;
-            std::size_t i = 0;
-            for (; i + 8 <= size; i += 8)
-            {
-                std::uint64_t w = 0;
-                std::memcpy(&w, data + i, 8);
-                h = (h ^ w) * 0x100000001B3ULL;
-                h ^= h >> 32u;
-            }
-            std::uint64_t w = 0;
-            if (i < size)
-            {
-                std::memcpy(&w, data + i, size - i);
-            }
-            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
-            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
-        }
-
-        void grow()
-        {
-            std::vector<slot> old(table.size() * 2);
-            old.swap(table);
-            const std::size_t mask = table.size() - 1;
-            for (const auto& s : old)
-            {
-                if (s.data != nullptr)
-                {
-                    std::size_t i = s.hash & mask;
-                    while (table[i].data != nullptr)
-                    {
-                        i = (i + 1) & mask;
-                    }
-                    table[i] = s;
-                }
-            }
-        }
-
-        std::vector<slot> table{};
-        std::size_t used = 0;
-        const char* last_data = nullptr;
-        std::size_t last_size = 0;
-    };
-
     /// @brief the length of the longest common prefix of the first @a limit bytes of @a a and @a b
     static std::size_t common_prefix_length(const char* a, const char* b, const std::size_t limit) noexcept
     {
@@ -1007,6 +874,354 @@ class json_pointer
         return i;
     }
 
+    /*!
+    @brief the prefixes of a flattened object that are marked as arrays, for
+           prefixes that are not short
+
+    A prefix is identified by the tokens it consists of: a node of a tree
+    stands for the prefix of its parent followed by a token, and is looked up
+    by its parent and the text of the token. The node of a prefix is found by
+    walking the tokens of the key from the root, so identifying all prefixes
+    of a key together costs one pass over the key, however long the prefixes
+    are, and no prefix is ever compared byte by byte as a whole. The nodes
+    along the key that was walked last are kept, and the walk of the next key
+    starts below the beginning it has in common with that key. The tree refers
+    to the keys, which must outlive it.
+    */
+    class prefix_tree
+    {
+      public:
+        /// @brief set the seed of the hash function, before anything is added
+        void reseed(const std::uint64_t seed_value) noexcept
+        {
+            seed = seed_value;
+        }
+
+        /// @brief mark the first @a prefix_size bytes of the key of @a key_size bytes at @a data
+        void mark(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            nodes[walk(data, key_size, prefix_size)].marked = true;
+            any_marked = true;
+        }
+
+        bool is_marked(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            return any_marked && nodes[walk(data, key_size, prefix_size)].marked;
+        }
+
+        bool empty() const noexcept
+        {
+            return !any_marked;
+        }
+
+        /// @brief the hash of the first @a size bytes at @a data, for the seed @a seed_value
+        static std::size_t hash_bytes(const char* data, std::size_t size, const std::uint64_t seed_value) noexcept
+        {
+            std::uint64_t h = seed_value ^ size;
+            std::size_t i = 0;
+            for (; i + 8 <= size; i += 8)
+            {
+                std::uint64_t w = 0;
+                std::memcpy(&w, data + i, 8);
+                h = (h ^ w) * 0x100000001B3ULL;
+                h ^= h >> 32u;
+            }
+            std::uint64_t w = 0;
+            if (i < size)
+            {
+                std::memcpy(&w, data + i, size - i);
+            }
+            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
+            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
+        }
+
+      private:
+        struct node
+        {
+            std::size_t parent = 0;
+            std::size_t hash = 0;
+            const char* token = nullptr;
+            std::size_t token_size = 0;
+            bool marked = false;
+        };
+
+        /// @brief a slot of the hash table; the index of a node, 0 if the slot is empty
+        struct bucket
+        {
+            std::size_t index = 0;
+        };
+
+        /// @brief the node after a token of the key that was walked last, and where the token ends
+        struct step
+        {
+            std::size_t node = 0;
+            std::size_t end = 0;
+        };
+
+        /// @brief the index of the node of the prefix that ends at the slash (or the end) at @a prefix_size
+        std::size_t walk(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            if (nodes.empty())
+            {
+                nodes.emplace_back();
+                table.resize(16);
+                chain.emplace_back();
+            }
+
+            if (data != last_key)
+            {
+                // keep the nodes within the beginning that this key has in common
+                // with the key they were found for; a prefix that ends inside a
+                // token of this key is not one of its prefixes
+                const std::size_t same = common_prefix_length(data, last_key, (std::min)(key_size, last_key_size));
+                std::size_t keep = chain.size();
+                while (keep > 1 && (chain[keep - 1].end > same || (chain[keep - 1].end == same && same < key_size && data[same] != '/')))
+                {
+                    --keep;
+                }
+                chain.resize(keep);
+                last_key = data;
+                last_key_size = key_size;
+            }
+
+            // walk the tokens that are not walked yet
+            while (chain.back().end < prefix_size && chain.back().end < key_size)
+            {
+                const std::size_t start = chain.back().end + 1;
+                const void* const slash = std::memchr(data + start, '/', key_size - start);
+                const std::size_t end = slash == nullptr ? key_size : static_cast<std::size_t>(static_cast<const char*>(slash) - data);
+                step next;
+                next.node = child(chain.back().node, data + start, end - start);
+                next.end = end;
+                chain.push_back(next);
+            }
+
+            if (chain.back().end == prefix_size)
+            {
+                return chain.back().node;
+            }
+            // an earlier call walked further
+            const auto it = std::lower_bound(chain.begin(), chain.end(), prefix_size, [](const step & s, std::size_t size)
+            {
+                return s.end < size;
+            });
+            return it->node;
+        }
+
+        std::size_t slot_of(std::size_t parent, std::size_t hash) const noexcept
+        {
+            std::uint64_t x = static_cast<std::uint64_t>(hash) ^ (static_cast<std::uint64_t>(parent) * 0x9E3779B97F4A7C15ULL);
+            x ^= x >> 32u;
+            x *= 0xD6E8FEB86659FD93ULL;
+            x ^= x >> 32u;
+            return static_cast<std::size_t>(x) & (table.size() - 1);
+        }
+
+        /// @brief the node of the prefix of the node @a parent followed by the token, which is added if it is not there
+        std::size_t child(std::size_t parent, const char* token, std::size_t token_size)
+        {
+            const std::size_t hash = hash_bytes(token, token_size, seed);
+            std::size_t i = slot_of(parent, hash);
+            while (table[i].index != 0)
+            {
+                const node& n = nodes[table[i].index];
+                if (n.parent == parent && n.hash == hash && n.token_size == token_size && std::memcmp(n.token, token, token_size) == 0)
+                {
+                    return table[i].index;
+                }
+                i = (i + 1) & (table.size() - 1);
+            }
+
+            node created;
+            created.parent = parent;
+            created.hash = hash;
+            created.token = token;
+            created.token_size = token_size;
+            nodes.push_back(created);
+            table[i].index = nodes.size() - 1;
+
+            // keep the load factor below 1/2
+            if (nodes.size() * 2 > table.size())
+            {
+                std::vector<bucket> old(table.size() * 2);
+                old.swap(table);
+                for (std::size_t k = 1; k < nodes.size(); ++k)
+                {
+                    std::size_t j = slot_of(nodes[k].parent, nodes[k].hash);
+                    while (table[j].index != 0)
+                    {
+                        j = (j + 1) & (table.size() - 1);
+                    }
+                    table[j].index = k;
+                }
+            }
+            return nodes.size() - 1;
+        }
+
+        std::uint64_t seed = 0;
+        /// @brief the nodes; the first is the root, the empty prefix
+        std::vector<node> nodes{};
+        /// @brief the nodes (not the root) in a hash table
+        std::vector<bucket> table{};
+        /// @brief the root, and the node after each token of the key that was walked last
+        std::vector<step> chain{};
+        const char* last_key = nullptr;
+        std::size_t last_key_size = 0;
+        bool any_marked = false;
+    };
+
+    /*!
+    @brief the pointer prefixes of a flattened object that denote arrays
+
+    @ref unflatten creates arrays exactly below the prefixes that have a
+    reference token 0 among their children, and objects everywhere else.
+    Deciding this up front keeps the result independent of the order in which
+    the flattened object is iterated, which is unspecified for some object
+    types.
+
+    A prefix is identified by the text of the key it is the beginning of:
+    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
+    The set refers to the keys, which must outlive it. Short prefixes are
+    kept in a hash table and compared as texts, which costs at most the length
+    of the bound. Longer prefixes are kept in a @ref prefix_tree, because
+    hashing and comparing every one of the prefixes of a key with many tokens
+    from its beginning would take quadratic time.
+
+    The hash function depends on a seed that is derived from the address of a
+    local variable, which address space layout randomization changes between
+    processes, so keys cannot be crafted to collide in advance; the result
+    does not depend on the seed. Where the addresses are not randomized, or
+    when the seed is known, keys can collide: k short prefixes then cost
+    k^2 / 2 comparisons of fewer than 64 bytes each. The long prefixes are not
+    hashed as a whole.
+    */
+    class array_prefix_set
+    {
+      public:
+        /// @brief choose the seed of the hash function, before anything is added: it is derived from the address that is passed
+        void reseed(const void* address) noexcept
+        {
+            // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast): the address is only a source of entropy
+            std::uint64_t x = static_cast<std::uint64_t>(reinterpret_cast<std::uintptr_t>(address)) ^ 0x9E3779B97F4A7C15ULL;
+            x *= 0xBF58476D1CE4E5B9ULL;
+            seed = x ^ (x >> 31u);
+            tree.reseed(seed);
+        }
+
+        /// @brief add the first @a prefix_size bytes of the key of @a key_size bytes at @a data
+        void insert(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            if (prefix_size >= short_limit)
+            {
+                tree.mark(data, key_size, prefix_size);
+                return;
+            }
+
+            // flattened objects are usually sorted, so most keys that have a
+            // 0 yield the prefix of the previous one
+            if (last_data != nullptr && last_size == prefix_size && std::memcmp(last_data, data, prefix_size) == 0)
+            {
+                return;
+            }
+            last_data = data;
+            last_size = prefix_size;
+
+            const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
+            if (table.empty())
+            {
+                table.resize(16);
+            }
+            const std::size_t mask = table.size() - 1;
+            std::size_t i = hash & mask;
+            while (table[i].data != nullptr)
+            {
+                if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
+                {
+                    return;
+                }
+                i = (i + 1) & mask;
+            }
+            table[i] = slot(hash, data, prefix_size);
+
+            // keep the load factor below 1/2
+            if (++used * 2 > table.size())
+            {
+                grow();
+            }
+        }
+
+        bool empty() const noexcept
+        {
+            return used == 0 && tree.empty();
+        }
+
+        /// @brief whether the first @a prefix_size bytes of the key of @a key_size bytes at @a data were added
+        bool contains(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            if (prefix_size >= short_limit)
+            {
+                return tree.is_marked(data, key_size, prefix_size);
+            }
+            if (used == 0)
+            {
+                return false;
+            }
+            const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
+            const std::size_t mask = table.size() - 1;
+            for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
+            {
+                if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
+                {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+      private:
+        /// @brief prefixes of fewer bytes are kept in the hash table
+        static constexpr std::size_t short_limit = 64;
+
+        struct slot
+        {
+            slot() noexcept = default;
+
+            slot(std::size_t h, const char* d, std::size_t s) noexcept
+                : hash(h), data(d), size(s)
+            {}
+
+            std::size_t hash = 0;
+            const char* data = nullptr; // nullptr: the slot is empty
+            std::size_t size = 0;
+        };
+
+        void grow()
+        {
+            std::vector<slot> old(table.size() * 2);
+            old.swap(table);
+            const std::size_t mask = table.size() - 1;
+            for (const auto& s : old)
+            {
+                if (s.data != nullptr)
+                {
+                    std::size_t i = s.hash & mask;
+                    while (table[i].data != nullptr)
+                    {
+                        i = (i + 1) & mask;
+                    }
+                    table[i] = s;
+                }
+            }
+        }
+
+        std::uint64_t seed = 0;
+        prefix_tree tree{};
+        std::vector<slot> table{};
+        std::size_t used = 0;
+        const char* last_data = nullptr;
+        std::size_t last_size = 0;
+    };
+
     /*!
     @brief check that @a key is a valid JSON pointer, and add the prefixes of
            it that denote arrays to @a arrays
@@ -1052,7 +1267,7 @@ class json_pointer
                 // a token 0 makes the pointer before it an array
                 if (i - begin == 1 && data[begin] == '0')
                 {
-                    arrays.insert(data, begin - 1);
+                    arrays.insert(data, size, begin - 1);
                 }
                 begin = i + 1;
             }
@@ -2062,6 +2277,7 @@ class json_pointer
         // token 0 among their children; the values below them are arrays,
         // all others are objects (see array_prefix_set)
         array_prefix_set arrays;
+        arrays.reseed(&arrays);
         const string_t* previous_key = nullptr;
         for (const auto& element : *value.m_data.m_value.object)
         {
@@ -2153,7 +2369,7 @@ class json_pointer
                     case detail::value_t::null:
                     {
                         // a first child 0 makes the value an array without a look-up
-                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, pos))
+                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, key.size(), pos))
                         {
                             // some reference token below this position is 0, so the
                             // value is an array

include/nlohmann/detail/output/binary_writer.hpp

@@ -1204,27 +1204,20 @@ class binary_writer
 
             // an optimized array of a valueless type carries no payload, so a
             // reader has nothing but the declared count to bound the allocation
-            // by. It refuses one array of more than max_valueless_container_size
-            // elements, and all such arrays of one input together when they add
-            // up to more than valueless_elements_base plus a number per byte
-            // read. Write the unoptimized form, at one byte per element, for
-            // an array that would exceed the base with the arrays written so
-            // far, so that the result can be read back: the limit of a reader
-            // is never below the base. Objects are not affected: every element
-            // is preceded by its key.
-            if (same_prefix && !(use_bjdata && is_bjdata_excluded_type_marker(first_prefix)))
+            // by and refuses an excessive one. Write the unoptimized form for
+            // those, at one byte per element, so the result can be read back.
+            // Objects are not affected: every element is preceded by its key.
+            const bool valueless_type = (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
+            const bool excessive_valueless = IsArray
+                                             && valueless_type
+                                             && size > detail::max_valueless_container_size;
+
+            if (same_prefix && !excessive_valueless
+                    && !(use_bjdata && is_bjdata_excluded_type_marker(first_prefix)))
             {
-                const bool valueless_type = IsArray && (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
-                if (!valueless_type || size <= detail::valueless_elements_base - valueless_elements_written)
-                {
-                    prefix_required = false;
-                    oa.write_character(to_char_type('$'));
-                    oa.write_character(first_prefix);
-                    if (valueless_type)
-                    {
-                        valueless_elements_written += size;
-                    }
-                }
+                prefix_required = false;
+                oa.write_character(to_char_type('$'));
+                oa.write_character(first_prefix);
             }
         }
 
@@ -5448,10 +5441,6 @@ class binary_writer
     /// how to treat a string value or object key that is not valid UTF-8
     /// (CBOR, MessagePack, UBJSON, BJData, and BSON; not BON8)
     const error_handler_t error_handler = binary_writer_default_error_handler();
-
-    /// UBJSON: the number of elements written so far in optimized arrays of a
-    /// valueless type, which a reader adds up and bounds
-    std::size_t valueless_elements_written = 0;
 };
 
 }  // namespace detail

single_include/nlohmann/json.hpp

@@ -18352,46 +18352,13 @@ the input.
 
 This is a sanity bound rather than a security boundary, and it is far above
 any container met in practice. @ref binary_writer falls back to the
-unoptimized encoding for longer containers, and for containers that together
-with the ones before them would exceed @ref valueless_elements_base, so that a
-value serialized by this library can always be read back.
+unoptimized encoding for longer containers, so that a value serialized by
+this library can always be read back.
 
 @sa https://github.com/nlohmann/json/issues/2793
 */
 JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 20;
 
-/*!
-@brief number of elements of valueless UBJSON containers accepted on top of
-       @ref valueless_elements_per_byte
-
-The limit @ref max_valueless_container_size applies to each container on its
-own, so on its own it lets 9 bytes announce 1048576 values, and every further
-9 bytes another 1048576. The elements of all containers of a valueless type
-in one input are therefore added up, and the sum must stay below this base
-plus @ref valueless_elements_per_byte for every byte read so far. The base is
-the per-container limit, so a container that was accepted on its own before
-the sum was introduced is still accepted at the start of an input.
-*/
-JSON_INLINE_VARIABLE constexpr std::size_t valueless_elements_base = max_valueless_container_size;
-
-/*!
-@brief number of elements of valueless UBJSON containers accepted per byte of
-       input, in addition to @ref valueless_elements_base
-
-An element of a value that has a payload costs at least one byte of input.
-Valueless elements are accepted at a rate of 4 per byte. A value takes 16
-bytes of memory in a DOM, so these arrays add about 80 bytes of memory per
-byte of input (measured: 77; one `Z` per byte needs about 32), beyond what the
-same bytes cost anyway, plus the base. This bounds the arrays of valueless
-type, not the memory of a whole document. Containers written by
-@ref binary_writer never need more than the base, because it writes an array
-in the unoptimized form once the typed arrays written so far and this one add
-up to more than that. The rate matters for input written by other encoders and
-by versions before 3.13.0 only; in the data this was measured on, no input has
-more than 0.17 elements per byte.
-*/
-JSON_INLINE_VARIABLE constexpr std::size_t valueless_elements_per_byte = 4;
-
 ///////////////////
 // binary reader //
 ///////////////////
@@ -22012,37 +21979,6 @@ class binary_reader
         return emit_unsigned(number);
     }
 
-    /*!
-    @brief add the elements of a container of a valueless type to the total of
-           the input and check the total against the input read so far
-
-    A container of type 'Z', 'T' or 'F' has no payload, so its elements are the
-    only ones for which the input does not bound the count. The check is made
-    once per container, not per element.
-
-    @param[in] count  number of elements the container declares; at most
-                      @ref max_valueless_container_size
-    @return false if the total is more than @ref valueless_elements_base plus
-            @ref valueless_elements_per_byte for every byte read so far; the
-            total is not changed then
-    */
-    bool charge_valueless_elements(const std::size_t count) noexcept
-    {
-        // the limit saturates instead of overflowing when size_t is 32 bits
-        // wide and a very large input has been read; valueless_elements
-        // never exceeds the limit, so the difference cannot underflow
-        constexpr std::size_t max_size = (std::numeric_limits<std::size_t>::max)();
-        const std::size_t limit = chars_read <= (max_size - valueless_elements_base) / valueless_elements_per_byte
-                                  ? valueless_elements_base + (valueless_elements_per_byte * chars_read)
-                                  : max_size;
-        if (JSON_HEDLEY_UNLIKELY(count > limit - valueless_elements))
-        {
-            return false;
-        }
-        valueless_elements += count;
-        return true;
-    }
-
     /*!
     @return whether array creation completed
     */
@@ -22128,27 +22064,24 @@ class binary_reader
             // declared count alone decides how much is allocated; the check is
             // made before the start event so that no container is opened that
             // is then abandoned. See @ref max_valueless_container_size.
-            if (JSON_HEDLEY_UNLIKELY(size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F'))
+            if (JSON_HEDLEY_UNLIKELY((size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F')
+                                     && size_and_type.first > max_valueless_container_size))
             {
-                if (JSON_HEDLEY_UNLIKELY(size_and_type.first > max_valueless_container_size))
-                {
-                    return out_of_range_error(exception_id::container_too_large, "excessive array size", "size");
-                }
-                if (JSON_HEDLEY_UNLIKELY(!charge_valueless_elements(size_and_type.first)))
-                {
-                    return out_of_range_error(exception_id::container_too_large, "excessive number of elements without payload", "size");
-                }
+                return out_of_range_error(exception_id::container_too_large, "excessive array size", "size");
             }
 
-            // a no-op is not a value, so an array of them is empty whatever
-            // count it declares: the SAX parser is told so, instead of being
-            // made to reserve storage for a count that no input backs
-            const std::size_t announced = size_and_type.second == 'N' ? 0 : size_and_type.first;
-            if (JSON_HEDLEY_UNLIKELY(!enter_array(announced, size_and_type.second)))
+            if (JSON_HEDLEY_UNLIKELY(!enter_array(size_and_type.first, size_and_type.second)))
             {
                 return false;
             }
 
+            if (size_and_type.second == 'N')
+            {
+                // a no-op is not a value, so a container of them holds none;
+                // the declared size has already been passed to the SAX parser
+                container_stack.back().remaining = 0;
+            }
+
             return size_and_type.second == 0
                    || parse_ubjson_typed_run(container_stack.back().remaining, size_and_type.second, std::integral_constant<bool, bulk_scan> {});
         }
@@ -23460,10 +23393,6 @@ class binary_reader
     /// the number of characters read
     std::size_t chars_read = 0;
 
-    /// UBJSON: the sum of the element counts of the containers of a valueless
-    /// type read so far; see @ref charge_valueless_elements
-    std::size_t valueless_elements = 0;
-
     /// whether we can assume little endianness
     const bool is_little_endian = little_endianness();
 
@@ -27098,139 +27027,6 @@ class json_pointer
     }
 
   private:
-    /*!
-    @brief the pointer prefixes of a flattened object that denote arrays
-
-    @ref unflatten creates arrays exactly below the prefixes that have a
-    reference token 0 among their children, and objects everywhere else.
-    Deciding this up front keeps the result independent of the order in which
-    the flattened object is iterated, which is unspecified for some object
-    types.
-
-    A prefix is identified by the text of the key it is the beginning of:
-    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
-    The set refers to the keys, which must outlive it.
-    */
-    class array_prefix_set
-    {
-      public:
-        void insert(const char* data, std::size_t size)
-        {
-            // flattened objects are usually sorted, so most keys that have a
-            // 0 yield the prefix of the previous one
-            if (last_data != nullptr && last_size == size && std::memcmp(last_data, data, size) == 0)
-            {
-                return;
-            }
-            last_data = data;
-            last_size = size;
-
-            if (table.empty())
-            {
-                table.resize(16);
-            }
-            const std::size_t hash = hash_of(data, size);
-            const std::size_t mask = table.size() - 1;
-            std::size_t i = hash & mask;
-            while (table[i].data != nullptr)
-            {
-                if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
-                {
-                    return;
-                }
-                i = (i + 1) & mask;
-            }
-            table[i] = slot(hash, data, size);
-
-            // keep the load factor below 1/2
-            if (++used * 2 > table.size())
-            {
-                grow();
-            }
-        }
-
-        bool empty() const noexcept
-        {
-            return used == 0;
-        }
-
-        bool contains(const char* data, std::size_t size) const noexcept
-        {
-            if (used == 0)
-            {
-                return false;
-            }
-            const std::size_t hash = hash_of(data, size);
-            const std::size_t mask = table.size() - 1;
-            for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
-            {
-                if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
-                {
-                    return true;
-                }
-            }
-            return false;
-        }
-
-      private:
-        struct slot
-        {
-            slot() noexcept = default;
-
-            slot(std::size_t h, const char* d, std::size_t s) noexcept
-                : hash(h), data(d), size(s)
-            {}
-
-            std::size_t hash = 0;
-            const char* data = nullptr; // nullptr: the slot is empty
-            std::size_t size = 0;
-        };
-
-        static std::size_t hash_of(const char* data, std::size_t size) noexcept
-        {
-            std::uint64_t h = 0x9E3779B97F4A7C15ULL ^ size;
-            std::size_t i = 0;
-            for (; i + 8 <= size; i += 8)
-            {
-                std::uint64_t w = 0;
-                std::memcpy(&w, data + i, 8);
-                h = (h ^ w) * 0x100000001B3ULL;
-                h ^= h >> 32u;
-            }
-            std::uint64_t w = 0;
-            if (i < size)
-            {
-                std::memcpy(&w, data + i, size - i);
-            }
-            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
-            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
-        }
-
-        void grow()
-        {
-            std::vector<slot> old(table.size() * 2);
-            old.swap(table);
-            const std::size_t mask = table.size() - 1;
-            for (const auto& s : old)
-            {
-                if (s.data != nullptr)
-                {
-                    std::size_t i = s.hash & mask;
-                    while (table[i].data != nullptr)
-                    {
-                        i = (i + 1) & mask;
-                    }
-                    table[i] = s;
-                }
-            }
-        }
-
-        std::vector<slot> table{};
-        std::size_t used = 0;
-        const char* last_data = nullptr;
-        std::size_t last_size = 0;
-    };
-
     /// @brief the length of the longest common prefix of the first @a limit bytes of @a a and @a b
     static std::size_t common_prefix_length(const char* a, const char* b, const std::size_t limit) noexcept
     {
@@ -27253,6 +27049,354 @@ class json_pointer
         return i;
     }
 
+    /*!
+    @brief the prefixes of a flattened object that are marked as arrays, for
+           prefixes that are not short
+
+    A prefix is identified by the tokens it consists of: a node of a tree
+    stands for the prefix of its parent followed by a token, and is looked up
+    by its parent and the text of the token. The node of a prefix is found by
+    walking the tokens of the key from the root, so identifying all prefixes
+    of a key together costs one pass over the key, however long the prefixes
+    are, and no prefix is ever compared byte by byte as a whole. The nodes
+    along the key that was walked last are kept, and the walk of the next key
+    starts below the beginning it has in common with that key. The tree refers
+    to the keys, which must outlive it.
+    */
+    class prefix_tree
+    {
+      public:
+        /// @brief set the seed of the hash function, before anything is added
+        void reseed(const std::uint64_t seed_value) noexcept
+        {
+            seed = seed_value;
+        }
+
+        /// @brief mark the first @a prefix_size bytes of the key of @a key_size bytes at @a data
+        void mark(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            nodes[walk(data, key_size, prefix_size)].marked = true;
+            any_marked = true;
+        }
+
+        bool is_marked(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            return any_marked && nodes[walk(data, key_size, prefix_size)].marked;
+        }
+
+        bool empty() const noexcept
+        {
+            return !any_marked;
+        }
+
+        /// @brief the hash of the first @a size bytes at @a data, for the seed @a seed_value
+        static std::size_t hash_bytes(const char* data, std::size_t size, const std::uint64_t seed_value) noexcept
+        {
+            std::uint64_t h = seed_value ^ size;
+            std::size_t i = 0;
+            for (; i + 8 <= size; i += 8)
+            {
+                std::uint64_t w = 0;
+                std::memcpy(&w, data + i, 8);
+                h = (h ^ w) * 0x100000001B3ULL;
+                h ^= h >> 32u;
+            }
+            std::uint64_t w = 0;
+            if (i < size)
+            {
+                std::memcpy(&w, data + i, size - i);
+            }
+            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
+            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
+        }
+
+      private:
+        struct node
+        {
+            std::size_t parent = 0;
+            std::size_t hash = 0;
+            const char* token = nullptr;
+            std::size_t token_size = 0;
+            bool marked = false;
+        };
+
+        /// @brief a slot of the hash table; the index of a node, 0 if the slot is empty
+        struct bucket
+        {
+            std::size_t index = 0;
+        };
+
+        /// @brief the node after a token of the key that was walked last, and where the token ends
+        struct step
+        {
+            std::size_t node = 0;
+            std::size_t end = 0;
+        };
+
+        /// @brief the index of the node of the prefix that ends at the slash (or the end) at @a prefix_size
+        std::size_t walk(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            if (nodes.empty())
+            {
+                nodes.emplace_back();
+                table.resize(16);
+                chain.emplace_back();
+            }
+
+            if (data != last_key)
+            {
+                // keep the nodes within the beginning that this key has in common
+                // with the key they were found for; a prefix that ends inside a
+                // token of this key is not one of its prefixes
+                const std::size_t same = common_prefix_length(data, last_key, (std::min)(key_size, last_key_size));
+                std::size_t keep = chain.size();
+                while (keep > 1 && (chain[keep - 1].end > same || (chain[keep - 1].end == same && same < key_size && data[same] != '/')))
+                {
+                    --keep;
+                }
+                chain.resize(keep);
+                last_key = data;
+                last_key_size = key_size;
+            }
+
+            // walk the tokens that are not walked yet
+            while (chain.back().end < prefix_size && chain.back().end < key_size)
+            {
+                const std::size_t start = chain.back().end + 1;
+                const void* const slash = std::memchr(data + start, '/', key_size - start);
+                const std::size_t end = slash == nullptr ? key_size : static_cast<std::size_t>(static_cast<const char*>(slash) - data);
+                step next;
+                next.node = child(chain.back().node, data + start, end - start);
+                next.end = end;
+                chain.push_back(next);
+            }
+
+            if (chain.back().end == prefix_size)
+            {
+                return chain.back().node;
+            }
+            // an earlier call walked further
+            const auto it = std::lower_bound(chain.begin(), chain.end(), prefix_size, [](const step & s, std::size_t size)
+            {
+                return s.end < size;
+            });
+            return it->node;
+        }
+
+        std::size_t slot_of(std::size_t parent, std::size_t hash) const noexcept
+        {
+            std::uint64_t x = static_cast<std::uint64_t>(hash) ^ (static_cast<std::uint64_t>(parent) * 0x9E3779B97F4A7C15ULL);
+            x ^= x >> 32u;
+            x *= 0xD6E8FEB86659FD93ULL;
+            x ^= x >> 32u;
+            return static_cast<std::size_t>(x) & (table.size() - 1);
+        }
+
+        /// @brief the node of the prefix of the node @a parent followed by the token, which is added if it is not there
+        std::size_t child(std::size_t parent, const char* token, std::size_t token_size)
+        {
+            const std::size_t hash = hash_bytes(token, token_size, seed);
+            std::size_t i = slot_of(parent, hash);
+            while (table[i].index != 0)
+            {
+                const node& n = nodes[table[i].index];
+                if (n.parent == parent && n.hash == hash && n.token_size == token_size && std::memcmp(n.token, token, token_size) == 0)
+                {
+                    return table[i].index;
+                }
+                i = (i + 1) & (table.size() - 1);
+            }
+
+            node created;
+            created.parent = parent;
+            created.hash = hash;
+            created.token = token;
+            created.token_size = token_size;
+            nodes.push_back(created);
+            table[i].index = nodes.size() - 1;
+
+            // keep the load factor below 1/2
+            if (nodes.size() * 2 > table.size())
+            {
+                std::vector<bucket> old(table.size() * 2);
+                old.swap(table);
+                for (std::size_t k = 1; k < nodes.size(); ++k)
+                {
+                    std::size_t j = slot_of(nodes[k].parent, nodes[k].hash);
+                    while (table[j].index != 0)
+                    {
+                        j = (j + 1) & (table.size() - 1);
+                    }
+                    table[j].index = k;
+                }
+            }
+            return nodes.size() - 1;
+        }
+
+        std::uint64_t seed = 0;
+        /// @brief the nodes; the first is the root, the empty prefix
+        std::vector<node> nodes{};
+        /// @brief the nodes (not the root) in a hash table
+        std::vector<bucket> table{};
+        /// @brief the root, and the node after each token of the key that was walked last
+        std::vector<step> chain{};
+        const char* last_key = nullptr;
+        std::size_t last_key_size = 0;
+        bool any_marked = false;
+    };
+
+    /*!
+    @brief the pointer prefixes of a flattened object that denote arrays
+
+    @ref unflatten creates arrays exactly below the prefixes that have a
+    reference token 0 among their children, and objects everywhere else.
+    Deciding this up front keeps the result independent of the order in which
+    the flattened object is iterated, which is unspecified for some object
+    types.
+
+    A prefix is identified by the text of the key it is the beginning of:
+    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
+    The set refers to the keys, which must outlive it. Short prefixes are
+    kept in a hash table and compared as texts, which costs at most the length
+    of the bound. Longer prefixes are kept in a @ref prefix_tree, because
+    hashing and comparing every one of the prefixes of a key with many tokens
+    from its beginning would take quadratic time.
+
+    The hash function depends on a seed that is derived from the address of a
+    local variable, which address space layout randomization changes between
+    processes, so keys cannot be crafted to collide in advance; the result
+    does not depend on the seed. Where the addresses are not randomized, or
+    when the seed is known, keys can collide: k short prefixes then cost
+    k^2 / 2 comparisons of fewer than 64 bytes each. The long prefixes are not
+    hashed as a whole.
+    */
+    class array_prefix_set
+    {
+      public:
+        /// @brief choose the seed of the hash function, before anything is added: it is derived from the address that is passed
+        void reseed(const void* address) noexcept
+        {
+            // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast): the address is only a source of entropy
+            std::uint64_t x = static_cast<std::uint64_t>(reinterpret_cast<std::uintptr_t>(address)) ^ 0x9E3779B97F4A7C15ULL;
+            x *= 0xBF58476D1CE4E5B9ULL;
+            seed = x ^ (x >> 31u);
+            tree.reseed(seed);
+        }
+
+        /// @brief add the first @a prefix_size bytes of the key of @a key_size bytes at @a data
+        void insert(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            if (prefix_size >= short_limit)
+            {
+                tree.mark(data, key_size, prefix_size);
+                return;
+            }
+
+            // flattened objects are usually sorted, so most keys that have a
+            // 0 yield the prefix of the previous one
+            if (last_data != nullptr && last_size == prefix_size && std::memcmp(last_data, data, prefix_size) == 0)
+            {
+                return;
+            }
+            last_data = data;
+            last_size = prefix_size;
+
+            const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
+            if (table.empty())
+            {
+                table.resize(16);
+            }
+            const std::size_t mask = table.size() - 1;
+            std::size_t i = hash & mask;
+            while (table[i].data != nullptr)
+            {
+                if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
+                {
+                    return;
+                }
+                i = (i + 1) & mask;
+            }
+            table[i] = slot(hash, data, prefix_size);
+
+            // keep the load factor below 1/2
+            if (++used * 2 > table.size())
+            {
+                grow();
+            }
+        }
+
+        bool empty() const noexcept
+        {
+            return used == 0 && tree.empty();
+        }
+
+        /// @brief whether the first @a prefix_size bytes of the key of @a key_size bytes at @a data were added
+        bool contains(const char* data, std::size_t key_size, std::size_t prefix_size)
+        {
+            if (prefix_size >= short_limit)
+            {
+                return tree.is_marked(data, key_size, prefix_size);
+            }
+            if (used == 0)
+            {
+                return false;
+            }
+            const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
+            const std::size_t mask = table.size() - 1;
+            for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
+            {
+                if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
+                {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+      private:
+        /// @brief prefixes of fewer bytes are kept in the hash table
+        static constexpr std::size_t short_limit = 64;
+
+        struct slot
+        {
+            slot() noexcept = default;
+
+            slot(std::size_t h, const char* d, std::size_t s) noexcept
+                : hash(h), data(d), size(s)
+            {}
+
+            std::size_t hash = 0;
+            const char* data = nullptr; // nullptr: the slot is empty
+            std::size_t size = 0;
+        };
+
+        void grow()
+        {
+            std::vector<slot> old(table.size() * 2);
+            old.swap(table);
+            const std::size_t mask = table.size() - 1;
+            for (const auto& s : old)
+            {
+                if (s.data != nullptr)
+                {
+                    std::size_t i = s.hash & mask;
+                    while (table[i].data != nullptr)
+                    {
+                        i = (i + 1) & mask;
+                    }
+                    table[i] = s;
+                }
+            }
+        }
+
+        std::uint64_t seed = 0;
+        prefix_tree tree{};
+        std::vector<slot> table{};
+        std::size_t used = 0;
+        const char* last_data = nullptr;
+        std::size_t last_size = 0;
+    };
+
     /*!
     @brief check that @a key is a valid JSON pointer, and add the prefixes of
            it that denote arrays to @a arrays
@@ -27298,7 +27442,7 @@ class json_pointer
                 // a token 0 makes the pointer before it an array
                 if (i - begin == 1 && data[begin] == '0')
                 {
-                    arrays.insert(data, begin - 1);
+                    arrays.insert(data, size, begin - 1);
                 }
                 begin = i + 1;
             }
@@ -28308,6 +28452,7 @@ class json_pointer
         // token 0 among their children; the values below them are arrays,
         // all others are objects (see array_prefix_set)
         array_prefix_set arrays;
+        arrays.reseed(&arrays);
         const string_t* previous_key = nullptr;
         for (const auto& element : *value.m_data.m_value.object)
         {
@@ -28399,7 +28544,7 @@ class json_pointer
                     case detail::value_t::null:
                     {
                         // a first child 0 makes the value an array without a look-up
-                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, pos))
+                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, key.size(), pos))
                         {
                             // some reference token below this position is 0, so the
                             // value is an array
@@ -30617,27 +30762,20 @@ class binary_writer
 
             // an optimized array of a valueless type carries no payload, so a
             // reader has nothing but the declared count to bound the allocation
-            // by. It refuses one array of more than max_valueless_container_size
-            // elements, and all such arrays of one input together when they add
-            // up to more than valueless_elements_base plus a number per byte
-            // read. Write the unoptimized form, at one byte per element, for
-            // an array that would exceed the base with the arrays written so
-            // far, so that the result can be read back: the limit of a reader
-            // is never below the base. Objects are not affected: every element
-            // is preceded by its key.
-            if (same_prefix && !(use_bjdata && is_bjdata_excluded_type_marker(first_prefix)))
+            // by and refuses an excessive one. Write the unoptimized form for
+            // those, at one byte per element, so the result can be read back.
+            // Objects are not affected: every element is preceded by its key.
+            const bool valueless_type = (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
+            const bool excessive_valueless = IsArray
+                                             && valueless_type
+                                             && size > detail::max_valueless_container_size;
+
+            if (same_prefix && !excessive_valueless
+                    && !(use_bjdata && is_bjdata_excluded_type_marker(first_prefix)))
             {
-                const bool valueless_type = IsArray && (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
-                if (!valueless_type || size <= detail::valueless_elements_base - valueless_elements_written)
-                {
-                    prefix_required = false;
-                    oa.write_character(to_char_type('$'));
-                    oa.write_character(first_prefix);
-                    if (valueless_type)
-                    {
-                        valueless_elements_written += size;
-                    }
-                }
+                prefix_required = false;
+                oa.write_character(to_char_type('$'));
+                oa.write_character(first_prefix);
             }
         }
 
@@ -34861,10 +34999,6 @@ class binary_writer
     /// how to treat a string value or object key that is not valid UTF-8
     /// (CBOR, MessagePack, UBJSON, BJData, and BSON; not BON8)
     const error_handler_t error_handler = binary_writer_default_error_handler();
-
-    /// UBJSON: the number of elements written so far in optimized arrays of a
-    /// valueless type, which a reader adds up and bounds
-    std::size_t valueless_elements_written = 0;
 };
 
 }  // namespace detail

tests/src/unit-json_pointer.cpp

@@ -23,8 +23,10 @@ using nlohmann::json;
     using namespace nlohmann::literals; // NOLINT(google-build-using-namespace)
 #endif
 
+#include <algorithm>
 #include <cerrno>
 #include <cstdlib>
+#include <ctime>
 #include <limits>
 #include <map>
 #include <random>
@@ -1560,3 +1562,294 @@ TEST_CASE("JSON patch with moves and copies")
     CHECK_THROWS_AS(inplace.patch_inplace(json::parse(R"([{"op":"move","from":"","path":""}])")), json::out_of_range&);
     CHECK(inplace == doc);
 }
+
+namespace
+{
+// the keys of a shape of flattened objects with long keys; `zero` is the
+// token that is repeated `m` times
+// 0: one key, 1: one `zero` followed by tokens 1, 2: the token 1 followed by
+// tokens `zero`, 3 and 4: two keys with a long prefix, apart from other keys,
+// 5: the same for two long branches, 6: more of the keys of 3
+std::vector<std::string> shape_keys(const int shape, const std::size_t m, const std::string& zero)
+{
+    std::string repeated;
+    for (std::size_t i = 0; i < m; ++i)
+    {
+        repeated += "/" + zero;
+    }
+    std::vector<std::string> keys;
+    switch (shape)
+    {
+        case 0:
+            keys.push_back(repeated);
+            break;
+        case 1:
+        {
+            std::string key = "/" + zero;
+            for (std::size_t i = 1; i < m; ++i)
+            {
+                key += "/1";
+            }
+            keys.push_back(key);
+            break;
+        }
+        case 2:
+        {
+            std::string key = "/1";
+            for (std::size_t i = 1; i < m; ++i)
+            {
+                key += "/" + zero;
+            }
+            keys.push_back(key);
+            break;
+        }
+        case 3:
+        case 4:
+            keys = {repeated + "/a0", "/10", repeated + "/a1", "/11"};
+            break;
+        case 5:
+            keys = {"/x" + repeated + "/a0", "/y" + repeated + "/a0", "/x" + repeated + "/a1", "/y" + repeated + "/a1"};
+            break;
+        case 6:
+            for (int j = 0; j < 4; ++j)
+            {
+                keys.push_back(repeated + "/a" + std::to_string(j));
+                keys.push_back("/1" + std::to_string(j));
+            }
+            break;
+        default:
+            break;
+    }
+    return keys;
+}
+
+// the best of `runs` times in seconds that std::clock() measures to unflatten the keys,
+// which an ordered_json holds in the order they are given (shape 4 uses a
+// json, which sorts them)
+double unflatten_cpu_time(const int shape, const std::size_t m, const int runs, const std::string& zero)
+{
+    const std::vector<std::string> keys = shape_keys(shape, m, zero);
+    nlohmann::ordered_json ordered = nlohmann::ordered_json::object();
+    json sorted = json::object();
+    for (const auto& key : keys)
+    {
+        ordered[key] = 1;
+        sorted[key] = 1;
+    }
+
+    double best = 1e30;
+    for (int i = 0; i < runs; ++i)
+    {
+        const std::clock_t start = std::clock();
+        if (shape == 4)
+        {
+            const json nested = sorted.unflatten();
+        }
+        else
+        {
+            const nlohmann::ordered_json nested = ordered.unflatten();
+        }
+        best = (std::min)(best, static_cast<double>(std::clock() - start) / static_cast<double>(CLOCKS_PER_SEC));
+    }
+    return best;
+}
+} // namespace
+
+TEST_CASE("unflatten of keys with many reference tokens")
+{
+    using nlohmann::ordered_json;
+
+    SECTION("which prefixes become arrays")
+    {
+        // sorted keys that share a long beginning
+        CHECK(json({{"/x/y/q/1", 5}, {"/x/y/w/0", 4}, {"/x/y/w/1", 3}, {"/x/y/z/0", 1}, {"/x/y/z/1", 2}}).unflatten() ==
+        json::parse(R"({"x":{"y":{"q":{"1":5},"w":[4,3],"z":[1,2]}}})"));
+
+        // prefixes that differ in the position of a slash only
+        CHECK(json({{"/a/0/x", 1}, {"/a/1/y", 3}, {"/ab/1", 2}}).unflatten() ==
+        json::parse(R"({"a":[{"x":1},{"y":3}],"ab":{"1":2}})"));
+        CHECK(json({{"/a/b/1", 1}, {"/ab/0", 2}}).unflatten() ==
+        json::parse(R"({"a":{"b":{"1":1}},"ab":[2]})"));
+
+        // tokens longer than one word, escapes, and a token 0 below a token 1
+        const std::string t = "token_with_more_than_eight_bytes";
+        CHECK(json({{"/" + t + "/1/b/0", 1}, {"/" + t + "/0", 2}, {"/" + t + "/2/a~1b", 3}}).unflatten() ==
+        json::parse(R"({"token_with_more_than_eight_bytes":[2,{"b":[1]},{"a/b":3}]})"));
+
+        // prefixes of more than 64 bytes, that share a long beginning
+        std::string deep;
+        json expected = {{"a", {1, 2}}, {"b", {{"1", 3}}}, {"c", {{"1", {{"x", {4}}}}}}};
+        for (int i = 0; i < 30; ++i)
+        {
+            deep += "/seg";
+            expected = {{"seg", expected}};
+        }
+        CHECK(json({{deep + "/c/1/x/0", 4}, {deep + "/a/1", 2}, {deep + "/b/1", 3}, {deep + "/a/0", 1}}).unflatten() == expected);
+        CHECK(json(ordered_json({{deep + "/c/1/x/0", 4}, {deep + "/a/1", 2}, {deep + "/b/1", 3}, {deep + "/a/0", 1}}).unflatten()) == expected);
+        CHECK(json(ordered_json({{deep + "/a/1", 2}, {deep + "/a/0", 1}, {deep + "/b/1", 3}, {deep + "/c/1/x/0", 4}}).unflatten()) == expected);
+
+        // prefixes of every length around the limit up to which they are hashed directly
+        for (std::size_t length = 40; length < 90; ++length)
+        {
+            const std::string name(length, 'x');
+            const json flat = {{"/" + name + "/a/0", 1}, {"/" + name + "/a/1", 2}, {"/" + name + "/b/1", 3}, {"/" + name + "/c/1/0", 4}};
+            CHECK(flat.unflatten() == json({{name, {{"a", {1, 2}}, {"b", {{"1", 3}}}, {"c", {{"1", {4}}}}}}}));
+        }
+
+        // only the parent of a token 0 is an array, however deep the key is
+        CHECK(json({{"/0/1/1/1", 1}}).unflatten() == json::parse(R"([{"1":{"1":{"1":1}}}])"));
+        CHECK(json({{"/1/1/1/0", 1}}).unflatten() == json::parse(R"({"1":{"1":{"1":[1]}}})"));
+        CHECK(json({{"/1/0/1/0", 1}}).unflatten() == json::parse(R"({"1":[{"1":[1]}]})"));
+    }
+
+    SECTION("the result does not depend on the order of the keys")
+    {
+        // random documents without empty containers and without the key "0" in
+        // an object: flatten() and unflatten() are inverse to each other
+        std::mt19937 gen(20261110); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
+        const std::vector<std::string> names = {"a", "b", "ab", "1", "2", "10", "a/b", "a~b", "token_with_more_than_eight_bytes", "x"};
+
+        struct builder
+        {
+            std::mt19937& gen;
+            const std::vector<std::string>& names;
+
+            json operator()(int depth) const
+            {
+                const int kind = std::uniform_int_distribution<int>(0, 9)(gen);
+                if (depth == 0 || kind < 3)
+                {
+                    return kind;
+                }
+                json result = kind < 6 ? json::array() : json::object();
+                const int size = std::uniform_int_distribution<int>(1, 4)(gen);
+                for (int i = 0; i < size; ++i)
+                {
+                    if (kind < 6)
+                    {
+                        result.push_back((*this)(depth - 1));
+                    }
+                    else
+                    {
+                        result[names[std::uniform_int_distribution<std::size_t>(0, names.size() - 1)(gen)]] = (*this)(depth - 1);
+                    }
+                }
+                return result;
+            }
+        };
+        const builder build{gen, names};
+
+        for (int round = 0; round < 200; ++round)
+        {
+            const json doc = build(6);
+            const json flat = doc.flatten();
+            CHECK(flat.unflatten() == doc);
+
+            // the same entries in shuffled order, in an object that keeps it
+            std::vector<std::pair<std::string, json>> entries;
+            for (const auto& el : flat.items())
+            {
+                entries.emplace_back(el.key(), el.value());
+            }
+            std::shuffle(entries.begin(), entries.end(), gen);
+            ordered_json shuffled = ordered_json::object();
+            for (const auto& e : entries)
+            {
+                shuffled[e.first] = e.second;
+            }
+            CHECK(json(shuffled.unflatten()) == doc);
+        }
+    }
+
+    SECTION("keys with long prefixes, in every order")
+    {
+        // prefixes of more than 64 bytes that share a long beginning, and
+        // continue with tokens that start the same way
+        std::string deep;
+        for (int i = 0; i < 30; ++i)
+        {
+            deep += "/seg";
+        }
+        const std::string other = deep.substr(0, 70) + "/x" + deep.substr(70);
+        std::vector<std::string> keys = {deep + "/a/0", deep + "/ab/1", deep + "/ab/x", deep + "/abc/0/y/0", other + "/b/1/0", deep + "/abc/1"};
+        std::sort(keys.begin(), keys.end());
+
+        // the result for the keys in sorted order, which json iterates in
+        json sorted = json::object();
+        for (const auto& key : keys)
+        {
+            sorted[key] = 1;
+        }
+        const json expected = sorted.unflatten();
+        CHECK(expected.is_object());
+
+        // ordered_json iterates in the order the keys were added
+        std::vector<std::size_t> order(keys.size());
+        for (std::size_t i = 0; i < order.size(); ++i)
+        {
+            order[i] = i;
+        }
+        std::size_t permutations = 0;
+        bool all_equal = true;
+        do
+        {
+            nlohmann::ordered_json flat = nlohmann::ordered_json::object();
+            for (const auto i : order)
+            {
+                flat[keys[i]] = 1;
+            }
+            all_equal = all_equal && json(flat.unflatten()) == expected;
+            ++permutations;
+        }
+        while (std::next_permutation(order.begin(), order.end()));
+        CHECK(permutations == 720);
+        CHECK(all_equal);
+    }
+
+    SECTION("time is linear in the number of tokens")
+    {
+        // A bound in seconds would depend on the machine. Instead, the time is
+        // compared with the time for the same keys with the token 0 replaced by
+        // a token that is not a number: there is no array, so no prefix is
+        // looked up. The ratio is 1 to 3 for a linear algorithm, and between
+        // 12 and 100 when looking up a prefix takes time proportional to its
+        // length. The time that std::clock() measures is mostly the time of the
+        // processor, which a busy machine does not inflate (on MSVC, it is the
+        // time that has passed), and the best of two or three runs counts.
+        for (int shape = 0; shape < 7; ++shape)
+        {
+            // the shapes with several keys, in an order that does not sort them,
+            // need more tokens to be slow enough to tell
+            const bool many = shape == 3 || shape == 5 || shape == 6;
+            const std::size_t m = many ? 40000 : 10000;
+            const int runs = many ? 2 : 3;
+
+            // a busy machine may spoil one comparison, hardly two
+            bool linear = false;
+            double t_array = 0;
+            double t_object = 0;
+            for (int attempt = 0; attempt < 2 && !linear; ++attempt)
+            {
+                t_array = unflatten_cpu_time(shape, m, runs, "0");
+                t_object = (std::max)(unflatten_cpu_time(shape, m, runs, "a"), 1e-3);
+                linear = t_array < 6 * t_object;
+            }
+            CAPTURE(shape)
+            CAPTURE(t_array)
+            CAPTURE(t_object)
+            CHECK(linear);
+        }
+
+        // the nesting is as expected: an array exactly below each token 0
+        const json nested_deep = json::object({{shape_keys(0, 1000, "0")[0], 1}}).unflatten();
+        std::size_t depth = 0;
+        for (const json* p = &nested_deep; p->is_array(); p = &p->back())
+        {
+            ++depth;
+        }
+        CHECK(depth == 1000);
+        const json nested_ones = json::object({{shape_keys(1, 1000, "0")[0], 1}}).unflatten();
+        CHECK(nested_ones.is_array());
+        CHECK(nested_ones.back().is_object());
+    }
+}

tests/src/unit-ubjson.cpp

@@ -19,12 +19,8 @@
 #include <nlohmann/json.hpp>
 using nlohmann::json;
 
-#include <cstdio>
 #include <iostream>
-#include <sstream>
-#include <utility>
 #include <fstream>
-#include <limits>
 #include <list>
 #include <set>
 #include "make_test_data_available.hpp"
@@ -2440,341 +2436,6 @@ TEST_CASE("UBJSON optimized arrays of a valueless type are bounded")
     }
 }
 
-namespace
-{
-/// SAX consumer that counts the values and keeps the id of a parse error
-struct ValuelessEventCounter : public nlohmann::json_sax<json>
-{
-    bool null() override
-    {
-        return ++values < stop_after;
-    }
-    bool boolean(bool /*val*/) override
-    {
-        return ++values < stop_after;
-    }
-    bool number_integer(json::number_integer_t /*val*/) override
-    {
-        ++values;
-        return true;
-    }
-    bool number_unsigned(json::number_unsigned_t /*val*/) override
-    {
-        ++values;
-        return true;
-    }
-    bool number_float(json::number_float_t /*val*/, const std::string& /*s*/) override
-    {
-        ++values;
-        return true;
-    }
-    bool string(std::string& /*val*/) override
-    {
-        ++values;
-        return true;
-    }
-    bool binary(json::binary_t& /*val*/) override
-    {
-        ++values;
-        return true;
-    }
-    bool start_object(std::size_t /*elements*/) override
-    {
-        return true;
-    }
-    bool key(std::string& /*val*/) override
-    {
-        return true;
-    }
-    bool end_object() override
-    {
-        return true;
-    }
-    bool start_array(std::size_t /*elements*/) override
-    {
-        return true;
-    }
-    bool end_array() override
-    {
-        return true;
-    }
-    bool parse_error(std::size_t /*position*/, const std::string& /*last_token*/, const json::exception& ex) override
-    {
-        error_id = ex.id;
-        return false;
-    }
-
-    /// the handler refuses the value that makes this many
-    std::size_t stop_after = (std::numeric_limits<std::size_t>::max)();
-    std::size_t values = 0;
-    int error_id = 0;
-};
-
-/// appends `[$<marker>#l<count>` (nine bytes) to @a v
-void append_valueless_array(std::vector<std::uint8_t>& v, const char marker, const std::uint32_t count)
-{
-    v.push_back('[');
-    v.push_back('$');
-    v.push_back(static_cast<std::uint8_t>(marker));
-    v.push_back('#');
-    v.push_back('l');
-    v.push_back(static_cast<std::uint8_t>(count >> 24));
-    v.push_back(static_cast<std::uint8_t>(count >> 16));
-    v.push_back(static_cast<std::uint8_t>(count >> 8));
-    v.push_back(static_cast<std::uint8_t>(count));
-}
-
-/// `[` followed by one `[$<marker>#l<count>` per entry of @a counts and `]`
-std::vector<std::uint8_t> valueless_arrays(const char marker, const std::vector<std::uint32_t>& counts)
-{
-    std::vector<std::uint8_t> v = {'['};
-    for (const auto count : counts)
-    {
-        append_valueless_array(v, marker, count);
-    }
-    v.push_back(']');
-    return v;
-}
-} // namespace
-
-TEST_CASE("UBJSON the valueless elements of a whole input are bounded")
-{
-    // The per-container limit alone let nine bytes (`[$Z#l` and a count of
-    // 1048576) announce a million values, and every further nine bytes another
-    // million. The elements of all containers of type 'Z', 'T' or 'F' in one
-    // input are now added up: they may not exceed 1048576 plus 4 for every
-    // byte read when the container's header has been read.
-    //
-    // The tests count events with a SAX handler where they can: building and
-    // comparing values of a million elements is what makes them slow under
-    // Valgrind, so there is one rejection and one round trip with a DOM.
-    json _;
-    const char* const budget_message = "[json.exception.out_of_range.408] syntax error while parsing UBJSON size: excessive number of elements without payload";
-
-    // two arrays that exceed the limit: the second one, with its header read
-    // at byte 19, may hold 4 * 19 = 76 values on top of the base of 1048576
-    const std::uint32_t over_first = 524288;
-    const std::uint32_t over_second = 1048576 + 76 - over_first + 1;
-
-    SECTION("the input of the original report is rejected")
-    {
-        // 362 bytes (40 arrays of 1048576 values) used to allocate 661 MB; the
-        // second array is the one that is refused
-        const auto input = valueless_arrays('Z', {over_first, over_second});
-        CHECK_THROWS_WITH_AS(_ = json::from_ubjson(input), budget_message, json::out_of_range&);
-    }
-
-    SECTION("every input adapter applies the budget")
-    {
-        const auto input = valueless_arrays('Z', {over_first, over_second});
-
-        // stream; not strict, which does not matter
-        std::stringstream stream;
-        stream.write(reinterpret_cast<const char*>(input.data()), static_cast<std::streamsize>(input.size()));
-        ValuelessEventCounter from_stream;
-        CHECK(!json::sax_parse(stream, &from_stream, json::input_format_t::ubjson, false));
-        CHECK(from_stream.error_id == 408);
-
-        // a container that is not contiguous; the counts of arrays of
-        // different types are added up
-        std::vector<std::uint8_t> mixed = {'['};
-        append_valueless_array(mixed, 'T', over_first);
-        append_valueless_array(mixed, 'F', over_second);
-        mixed.push_back(']');
-        const std::list<std::uint8_t> as_list(mixed.begin(), mixed.end());
-        ValuelessEventCounter from_list;
-        CHECK(!json::sax_parse(as_list.begin(), as_list.end(), &from_list, json::input_format_t::ubjson));
-        CHECK(from_list.error_id == 408);
-        CHECK(from_list.values == over_first);
-
-        // FILE*
-        FILE* const file = std::tmpfile(); // NOLINT(cppcoreguidelines-owning-memory)
-        REQUIRE(file != nullptr);
-        CHECK(std::fwrite(input.data(), 1, input.size(), file) == input.size());
-        std::rewind(file);
-        ValuelessEventCounter from_file;
-        CHECK(!json::sax_parse(file, &from_file, json::input_format_t::ubjson));
-        CHECK(from_file.error_id == 408);
-        std::fclose(file); // NOLINT(cert-err33-c,cppcoreguidelines-owning-memory)
-    }
-
-    SECTION("the limit is exact and the bytes read raise it")
-    {
-        // [ [$Z#l 524288] [$U#l 4096 + 4096 bytes] [$Z#l count] ]: chars_read
-        // is 1 + 9 + (9 + 4096) + 9 = 4124 when the last header has been read,
-        // so the last array may hold 4 * 4124 = 16496 values on top of the
-        // base of 1048576 less the 524288 of the first array
-        const std::uint32_t last_allowed = 1048576 + 16496 - 524288;
-        for (const std::uint32_t count :
-                {
-                    last_allowed, last_allowed + 1
-                })
-        {
-            CAPTURE(count)
-            std::vector<std::uint8_t> input = {'['};
-            append_valueless_array(input, 'Z', 524288);
-            input.insert(input.end(), {'[', '$', 'U', '#', 'l', 0x00, 0x00, 0x10, 0x00});
-            input.insert(input.end(), 4096, 0x01);
-            append_valueless_array(input, 'Z', count);
-            input.push_back(']');
-            ValuelessEventCounter sax;
-            const bool accepted = count == last_allowed;
-            CHECK(json::sax_parse(input, &sax, json::input_format_t::ubjson) == accepted);
-            CHECK(sax.error_id == (accepted ? 0 : 408));
-            CHECK(sax.values == 524288u + 4096u + (accepted ? count : 0u));
-        }
-
-        // an array of 1048576 values on its own is accepted as before
-        const std::vector<std::uint8_t> single = {'[', '$', 'Z', '#', 'l', 0x00, 0x10, 0x00, 0x00};
-        // (the handler ends the parse at the first value, so that the million
-        // values are not read)
-        ValuelessEventCounter sax;
-        sax.stop_after = 1;
-        CHECK(!json::sax_parse(single, &sax, json::input_format_t::ubjson));
-        CHECK(sax.error_id == 0);
-        CHECK(sax.values == 1);
-    }
-
-    SECTION("to_ubjson writes the typed form up to the base only")
-    {
-        // 1048 rows of 1000 values fit under the base of 1048576, the 1049th
-        // would not: its elements are written one by one. Written all typed,
-        // 1100 rows of 6 bytes would be refused by a reader (1075 rows are the
-        // most it accepts). The rows hold null, true or false, and the
-        // fallback does not depend on which
-        std::vector<std::uint8_t> encoded;
-        {
-            json table = json::array();
-            for (int row = 0; row < 1100; ++row)
-            {
-                const json cell = row % 3 == 0 ? json(nullptr) : json(row % 3 == 1);
-                table.push_back(json(1000, cell));
-            }
-            encoded = json::to_ubjson(table, true, true);
-        }
-        // outer array: `[$[#I` and the count (7 bytes), then 1048 typed rows of 6
-        // bytes (`$Z#I` and two bytes) and 52 rows of `#I`, two bytes, and 1000 `Z`
-        CHECK(encoded.size() == 7 + (1048 * 6) + (52 * (4 + 1000)));
-
-        // the output is read back
-        ValuelessEventCounter sax;
-        CHECK(json::sax_parse(encoded, &sax, json::input_format_t::ubjson));
-        CHECK(sax.error_id == 0);
-        CHECK(sax.values == 1100u * 1000u);
-    }
-
-    SECTION("BJData is not affected")
-    {
-        // BJData has no optimized arrays of these types, and the writer does
-        // not charge them
-        json table = json::array();
-        for (int row = 0; row < 3; ++row)
-        {
-            table.push_back(json(10, nullptr));
-        }
-        const auto encoded = json::to_bjdata(table, true, true);
-        CHECK(json::from_bjdata(encoded) == table);
-
-        const std::vector<std::uint8_t> input = {'[', '$', 'Z', '#', 'l', 0x00, 0x10, 0x00, 0x00};
-        CHECK_THROWS_AS(_ = json::from_bjdata(input), json::parse_error&);
-    }
-
-    SECTION("an object of a valueless type needs a key for every value")
-    {
-        // an object member costs a key, so the count is bounded by the input
-        // and is not charged to the budget
-        const std::vector<std::uint8_t> input = {'{', '$', 'Z', '#', 'l', 0x00, 0x10, 0x00, 0x00};
-        ValuelessEventCounter sax;
-        CHECK(!json::sax_parse(input, &sax, json::input_format_t::ubjson));
-        CHECK(sax.error_id == 110);
-        CHECK(sax.values == 0);
-    }
-}
-
-TEST_CASE("UBJSON an optimized array of no-ops is empty whatever its count")
-{
-    // A no-op ('N') is not a value, so `[$N#<n>` is an array without elements
-    // for every n. The count used to be passed on to the SAX parser, which
-    // told it to expect n elements, and the DOM parser reserved storage for
-    // them: 16384 values (256 KB) for a count of 2^31 in 9 bytes of input.
-    SECTION("the SAX parser is told that the array is empty")
-    {
-        for (const std::vector<std::uint8_t>& input :
-                {
-                    std::vector<std::uint8_t> {'[', '$', 'N', '#', 'i', 2},
-                    std::vector<std::uint8_t> {'[', '$', 'N', '#', 'I', 0x7F, 0xFF},
-                    std::vector<std::uint8_t> {'[', '$', 'N', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF},
-                    std::vector<std::uint8_t> {'[', '$', 'N', '#', 'i', 0}
-                })
-        {
-            SaxEventLogger logger;
-            CHECK(json::sax_parse(input, &logger, json::input_format_t::ubjson));
-            CHECK(logger.events == std::vector<std::string>({"start_array(0)", "end_array()"}));
-        }
-
-        // between other values, the next value is read as usual
-        const std::vector<std::uint8_t> nested = {'[', '[', '$', 'N', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF, 'T', '[', '$', 'N', '#', 'i', 3, ']'};
-        SaxEventLogger logger;
-        CHECK(json::sax_parse(nested, &logger, json::input_format_t::ubjson));
-        CHECK(logger.events == std::vector<std::string>({"start_array()", "start_array(0)", "end_array()", "boolean(true)", "start_array(0)", "end_array()", "end_array()"}));
-    }
-
-    SECTION("the DOM parser reserves nothing")
-    {
-        // 2000 arrays of 9 bytes that announce 2^31 elements each: with a
-        // reservation of 16384 values per array this took about 500 MB
-        std::vector<std::uint8_t> input = {'['};
-        for (int i = 0; i < 2000; ++i)
-        {
-            input.insert(input.end(), {'[', '$', 'N', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF});
-        }
-        input.push_back(']');
-
-        const json j = json::from_ubjson(input);
-        REQUIRE(j.size() == 2000);
-        std::size_t capacity = 0;
-        for (const auto& element : j)
-        {
-            CHECK(element.is_array());
-            CHECK(element.empty());
-            capacity += element.get_ref<const json::array_t&>().capacity();
-        }
-        CHECK(capacity == 0);
-
-        // the 7-byte form inside an optimized array of arrays
-        std::vector<std::uint8_t> typed = {'[', '$', '[', '#', 'I', 0x07, 0xD0};
-        for (int i = 0; i < 2000; ++i)
-        {
-            typed.insert(typed.end(), {'$', 'N', '#', 'I', 0x7F, 0xFF});
-        }
-        const json k = json::from_ubjson(typed);
-        REQUIRE(k.size() == 2000);
-        capacity = 0;
-        for (const auto& element : k)
-        {
-            CHECK(element.empty());
-            capacity += element.get_ref<const json::array_t&>().capacity();
-        }
-        CHECK(capacity == 0);
-    }
-
-    SECTION("a count that no container could hold is no longer an error")
-    {
-        // the array is empty, so nothing has to fit: 0x7FFFFFFF used to be
-        // reported as out_of_range.408 where it exceeds the maximum size of
-        // an array, and is accepted now
-        const std::vector<std::uint8_t> input = {'[', '$', 'N', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF};
-        CHECK(json::from_ubjson(input) == json::array());
-
-        // a count that does not fit into std::size_t still is
-#if SIZE_MAX == 0xffffffff
-        const std::vector<std::uint8_t> too_large = {'[', '$', 'N', '#', 'L', 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00};
-        json _;
-        CHECK_THROWS_AS(_ = json::from_ubjson(too_large), json::out_of_range&);
-#endif
-    }
-}
-
 TEST_CASE("issue #5405 - array reserve for definite-length UBJSON arrays")
 {
 #if !defined(JSON_NOEXCEPTION)