Report a missing 0xFF after a final BON8 string also without strict

A BON8 string ends at the first byte that cannot continue it. When a
string ends a value and is not terminated by 0xFF, that byte belongs to
whatever follows the value, but the reader has already taken it from the
input and keeps it in its push-back buffer. With strict = true the
end-of-input check reports it; with strict = false the buffer was
discarded, so a following value in a stream lost its first byte or bytes
without an error ({0x61, 0x90} read "a" and then dropped the 0 that
follows).

Report parse_error.110 "string at the end of the value is not terminated
by 0xFF" when the push-back buffer is not empty once a BON8 value is
complete and strict is false, as bon8.md requires the final 0xFF. Output
of to_bon8 always has it, so canonical input is not affected.

Fixes #6110.

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

docs/mkdocs/docs/api/basic_json/from_bon8.md

@@ -69,8 +69,10 @@ Strong guarantee: if an exception is thrown, there are no changes in the JSON va
 
 ## Exceptions
 
-- Throws [parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110) if the given input ends prematurely or
-  the end of the file was not reached when `strict` was set to true
+- Throws [parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110) if the given input ends prematurely,
+  if the end of the file was not reached when `strict` was set to true, or if a string at the end of the value is not
+  terminated by 0xFF although a byte follows it (also when `strict` is false: the byte that ends the string is
+  taken from the input, so the next value would be lost)
 - Throws [parse_error.112](../../home/exceptions.md#jsonexceptionparse_error112) if a parse error occurs, for instance
   an invalid byte, a string that is not valid UTF-8, or an object key that is not a string
 

docs/mkdocs/docs/api/basic_json/unflatten.md

@@ -26,8 +26,7 @@ The function can throw the following exceptions:
 - Throws [`type_error.314`](../../home/exceptions.md#jsonexceptiontype_error314) if value is not an object
 - Throws [`type_error.315`](../../home/exceptions.md#jsonexceptiontype_error315) if object values are not primitive
 - Throws [`type_error.313`](../../home/exceptions.md#jsonexceptiontype_error313) if a key (JSON pointer) leads to a
-  conflicting nesting, for example if a key with a value other than `#!json null` is a prefix of another key (as `/a`
-  and `/a/b`), in whichever order the keys come; example: `"invalid value to unflatten"`
+  conflicting nesting; example: `"invalid value to unflatten"`
 - Throws [`parse_error.106`](../../home/exceptions.md#jsonexceptionparse_error106) if an array index in a key begins
   with '0'; example: `"array index '01' must not begin with '0'"`
 - Throws [`parse_error.107`](../../home/exceptions.md#jsonexceptionparse_error107) if a key is not empty and does not
@@ -91,6 +90,3 @@ Apart from these three cases, for a JSON value `j`, the following is always true
 - Throws [`parse_error.109`](../../home/exceptions.md#jsonexceptionparse_error109) instead of
   [`out_of_range.404`](../../home/exceptions.md#jsonexceptionout_of_range404) for a one-character array index that is
   not a digit (e.g., `/x`) in version 3.13.0, as it already did for longer ones.
-- Throws [`type_error.313`](../../home/exceptions.md#jsonexceptiontype_error313) for a key that is a prefix of an
-  earlier key in version 3.13.0; before, an object type that keeps the insertion order (such as
-  [`ordered_json`](../ordered_json.md)) silently replaced the nested value.

docs/mkdocs/docs/features/binary_formats/bon8.md

@@ -181,7 +181,10 @@ of the message are reported as [parse_error.110](../../home/exceptions.md#jsonex
     arrays and objects with up to four elements that are terminated by 0xFE, unsorted object keys, or a 0xFF after a
     string that would also end without it, are accepted. A second 0xFF is not a terminator but an empty string.
 
-    Strings must be valid UTF-8, and a string at the very end of a message must be terminated by 0xFF.
+    Strings must be valid UTF-8, and a string at the very end of a message must be terminated by 0xFF. This also
+    holds when `strict` is false and more data follows the value: the byte that would end the string belongs to the
+    next value, and reading it would remove it from the input, so the missing 0xFF is reported as
+    [parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110).
 
     Duplicate object keys are accepted; the last value wins (`ordered_json` keeps the position of the first occurrence).
     The specification does not say how to treat them; the HikoGUI reference decoder keeps the first value.

include/nlohmann/detail/input/binary_reader.hpp

@@ -177,6 +177,17 @@ class binary_reader
                 JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert) LCOV_EXCL_LINE
         }
 
+        // BON8: a string ends at the first byte that cannot continue it. If
+        // that byte follows the value, the reader has already taken it from
+        // the input and holds it in bon8_pushback. Without the end-of-input
+        // check below it would be dropped, and the next read would start
+        // behind it, so report the missing 0xFF instead.
+        if (result && !strict && input_format == input_format_t::bon8 && bon8_pushback_size != 0)
+        {
+            get_bon8();
+            return last_byte_error(exception_id::unexpected_end_of_input, "string at the end of the value is not terminated by 0xFF", "value", "");
+        }
+
         // strict mode: next byte must be EOF
         if (result && strict)
         {

include/nlohmann/detail/json_pointer.hpp

@@ -852,6 +852,139 @@ 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
     {
@@ -874,355 +1007,6 @@ 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,hicpp-use-auto,modernize-use-auto): the address is only a source of entropy
-            std::uint64_t x = reinterpret_cast<std::uintptr_t>(address);
-            x ^= 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
@@ -1268,7 +1052,7 @@ class json_pointer
                 // a token 0 makes the pointer before it an array
                 if (i - begin == 1 && data[begin] == '0')
                 {
-                    arrays.insert(data, size, begin - 1);
+                    arrays.insert(data, begin - 1);
                 }
                 begin = i + 1;
             }
@@ -2311,7 +2095,6 @@ 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)
         {
@@ -2403,7 +2186,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, key.size(), pos))
+                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, pos))
                         {
                             // some reference token below this position is 0, so the
                             // value is an array
@@ -2455,19 +2238,6 @@ class json_pointer
                 pos = end;
             }
 
-            if (JSON_HEDLEY_UNLIKELY(!current->is_null()))
-            {
-                // the key is a prefix of an earlier key (only possible if the
-                // object type does not sort its keys), so the value is the
-                // array or object built for that key: a null leaves it as it
-                // is (as when the shorter key comes first), any other value
-                // conflicts with it
-                if (element.second.is_null())
-                {
-                    continue;
-                }
-                JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_invalid_value, "invalid value to unflatten", &result));
-            }
             *current = element.second;
         }
 

single_include/nlohmann/json.hpp

@@ -18568,6 +18568,17 @@ class binary_reader
                 JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert) LCOV_EXCL_LINE
         }
 
+        // BON8: a string ends at the first byte that cannot continue it. If
+        // that byte follows the value, the reader has already taken it from
+        // the input and holds it in bon8_pushback. Without the end-of-input
+        // check below it would be dropped, and the next read would start
+        // behind it, so report the missing 0xFF instead.
+        if (result && !strict && input_format == input_format_t::bon8 && bon8_pushback_size != 0)
+        {
+            get_bon8();
+            return last_byte_error(exception_id::unexpected_end_of_input, "string at the end of the value is not terminated by 0xFF", "value", "");
+        }
+
         // strict mode: next byte must be EOF
         if (result && strict)
         {
@@ -27139,6 +27150,139 @@ 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
     {
@@ -27161,355 +27305,6 @@ 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,hicpp-use-auto,modernize-use-auto): the address is only a source of entropy
-            std::uint64_t x = reinterpret_cast<std::uintptr_t>(address);
-            x ^= 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
@@ -27555,7 +27350,7 @@ class json_pointer
                 // a token 0 makes the pointer before it an array
                 if (i - begin == 1 && data[begin] == '0')
                 {
-                    arrays.insert(data, size, begin - 1);
+                    arrays.insert(data, begin - 1);
                 }
                 begin = i + 1;
             }
@@ -28598,7 +28393,6 @@ 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)
         {
@@ -28690,7 +28484,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, key.size(), pos))
+                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, pos))
                         {
                             // some reference token below this position is 0, so the
                             // value is an array
@@ -28742,19 +28536,6 @@ class json_pointer
                 pos = end;
             }
 
-            if (JSON_HEDLEY_UNLIKELY(!current->is_null()))
-            {
-                // the key is a prefix of an earlier key (only possible if the
-                // object type does not sort its keys), so the value is the
-                // array or object built for that key: a null leaves it as it
-                // is (as when the shorter key comes first), any other value
-                // conflicts with it
-                if (element.second.is_null())
-                {
-                    continue;
-                }
-                JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_invalid_value, "invalid value to unflatten", &result));
-            }
             *current = element.second;
         }
 

tests/src/unit-bon8.cpp

@@ -608,14 +608,26 @@ TEST_CASE("BON8")
             CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec), "[json.exception.parse_error.110] parse error at byte 2: syntax error while parsing BON8 value: expected end of input; last byte: 0x90", json::parse_error&);
             CHECK(json::from_bon8(vec, true, false).is_discarded());
 
-            // the byte after a string that ends a container
+            // the byte after a string that ends a container: without strict, the
+            // missing 0xFF is reported, as the byte has been taken from the input
             const bytes vec2 = {0x81, 'a', 0x90};
-            CHECK(json::from_bon8(vec2, false) == json({"a"}));
+            CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec2, false), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0x90", json::parse_error&);
+            CHECK(json::from_bon8(vec2, false, false).is_discarded());
             CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec2), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: expected end of input; last byte: 0x90", json::parse_error&);
 
             const bytes vec3 = {0x81, 'a', 0xC2, 0x00};
-            CHECK(json::from_bon8(vec3, false) == json({"a"}));
+            CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec3, false), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0xC2", json::parse_error&);
             CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec3), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: expected end of input; last byte: 0xC2", json::parse_error&);
+
+            // with a terminated string, strict = false leaves the next value in the stream
+            std::istringstream terminated(std::string("\x61\xFF\x90", 3));
+            CHECK(json::from_bon8(terminated, false) == "a");
+            CHECK(terminated.tellg() == 2);
+            CHECK(json::from_bon8(terminated, false) == 0);
+
+            // without the terminator, the next value would be lost
+            std::istringstream unterminated(std::string("\x61\x90", 2));
+            CHECK_THROWS_WITH_AS(_ = json::from_bon8(unterminated, false), "[json.exception.parse_error.110] parse error at byte 2: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0x90", json::parse_error&);
         }
     }
 

tests/src/unit-json_pointer.cpp

@@ -23,10 +23,8 @@ 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>
@@ -1240,34 +1238,6 @@ TEST_CASE("flatten of structured values")
         CHECK(flat_object.unflatten() == nlohmann::ordered_json::parse(R"({"b": {"1": 2}})"));
     }
 
-#if !defined(JSON_NOEXCEPTION)
-    SECTION("unflatten with a key that is a prefix of an earlier key")
-    {
-        // json visits the shorter key first; ordered_json may see it last
-        CHECK_THROWS_WITH_AS(nlohmann::ordered_json::parse(R"({"/a/b":2,"/a":1})").unflatten(),
-                             "[json.exception.type_error.313] invalid value to unflatten", nlohmann::ordered_json::type_error&);
-        CHECK_THROWS_WITH_AS(nlohmann::ordered_json::parse(R"({"/a/0/b":1,"/a/0":2})").unflatten(),
-                             "[json.exception.type_error.313] invalid value to unflatten", nlohmann::ordered_json::type_error&);
-        CHECK_THROWS_WITH_AS(nlohmann::ordered_json::parse(R"({"/x":1,"":2})").unflatten(),
-                             "[json.exception.type_error.313] invalid value to unflatten", nlohmann::ordered_json::type_error&);
-
-        // the same members in the other order
-        CHECK_THROWS_WITH_AS(nlohmann::ordered_json::parse(R"({"/a":1,"/a/b":2})").unflatten(),
-                             "[json.exception.type_error.313] invalid value to unflatten", nlohmann::ordered_json::type_error&);
-        CHECK_THROWS_WITH_AS(json::parse(R"({"/a/b":2,"/a":1})").unflatten(),
-                             "[json.exception.type_error.313] invalid value to unflatten", json::type_error&);
-    }
-#endif
-
-    SECTION("unflatten with a null at a key that is a prefix of another key")
-    {
-        // the null keeps the container, whichever key comes first
-        CHECK(nlohmann::ordered_json::parse(R"({"/a/b":2,"/a":null})").unflatten() == nlohmann::ordered_json::parse(R"({"a":{"b":2}})"));
-        CHECK(nlohmann::ordered_json::parse(R"({"/a":null,"/a/b":2})").unflatten() == nlohmann::ordered_json::parse(R"({"a":{"b":2}})"));
-        CHECK(nlohmann::ordered_json::parse(R"({"/a/0":1,"/a":null})").unflatten() == nlohmann::ordered_json::parse(R"({"a":[1]})"));
-        CHECK(json::parse(R"({"/a/b":2,"/a":null})").unflatten() == json::parse(R"({"a":{"b":2}})"));
-    }
-
 #if !defined(JSON_NOEXCEPTION)
     SECTION("an object with the key \"0\" next to a non-index key does not round-trip")
     {
@@ -1590,294 +1560,3 @@ 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());
-    }
-}