Throw type_error.313 when an unflatten key is a prefix of an earlier key

With an object type that keeps the insertion order (ordered_json), a key
such as "/a" can come after "/a/b". The final assignment then replaced the
object built for "/a/b" without an error, so {"/a/b":2,"/a":1} gave
{"a":1}. json never saw this because std::map visits the shorter key first.

Throw type_error.313 if the target of the final assignment is no longer
null, as json does for the same members. A null value keeps the container,
so {"/a/b":2,"/a":null} gives {"a":{"b":2}} for both object types.

Fixes #6105.

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

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

@@ -26,7 +26,8 @@ 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; example: `"invalid value to unflatten"`
+  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"`
 - 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
@@ -90,3 +91,6 @@ 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/home/exceptions.md

@@ -140,8 +140,6 @@ Exceptions have ids 1xx.
 
 This error indicates a syntax error while deserializing a JSON text. The error message describes that an unexpected token (character) was encountered, and the member `byte` indicates the error position.
 
-The message ends with the last read token (`last read: '...'`), with control characters written as `<U+XXXX>`. A token of more than 8192 characters is shown by its first and its last 4096 characters, separated by `...`.
-
 !!! failure "Example message"
 
     Input ended prematurely:

include/nlohmann/detail/input/input_adapters.hpp

@@ -110,164 +110,87 @@ inline const char* empty_input_message() noexcept
     return "attempting to parse an empty input; check that your input string or stream contains the expected JSON";
 }
 
+////////////////////
+// input adapters //
+////////////////////
+
+#ifndef JSON_NO_IO
 /*!
-@brief the characters of the last read token, kept for error messages
-
 A growable array of characters for the part of a token that an input adapter
-copied out of its window, or that the lexer copies while it scans input it
+copied out of its window: unlike std::vector<char>::push_back(), appending a
-cannot read again: unlike std::vector::push_back(), appending a character
+character takes no reference to a local, and is a few instructions when there
-takes no reference to a local, and is a few instructions when there is room.
+is room.
-
-The token is only needed for error messages, which show its first head()
-characters and its last head() characters (see lexer::get_token_string). The
-buffer therefore keeps the first head() and at least the last tail()
-characters: when it is full and holds more than limit() characters, it drops
-the characters in between instead of growing. That happens where it would
-otherwise reallocate, so appending stays as cheap as before, and a long string
-or a long run of whitespace read from a stream is not kept a second time.
 */
-template<typename CharType>
+class token_carry_buffer
-class token_text_buffer
 {
   public:
-    static constexpr std::size_t head() noexcept
+    token_carry_buffer() = default;
-    {
+    token_carry_buffer(const token_carry_buffer&) = delete;
-        return 4096;
+    token_carry_buffer& operator=(const token_carry_buffer&) = delete;
-    }
+    token_carry_buffer(token_carry_buffer&& rhs) noexcept
-    /// a little more than head(), as the last character may be handed back
-    static constexpr std::size_t tail() noexcept
-    {
-        return head() + 16;
-    }
-    static constexpr std::size_t limit() noexcept
-    {
-        return head() + (2 * tail());
-    }
-
-    token_text_buffer() = default;
-    token_text_buffer(const token_text_buffer&) = delete;
-    token_text_buffer& operator=(const token_text_buffer&) = delete;
-    token_text_buffer(token_text_buffer&& rhs) noexcept
         : m_data(std::move(rhs.m_data)), m_end(rhs.m_end), m_capacity_end(rhs.m_capacity_end)
     {
         rhs.m_end = rhs.m_capacity_end = nullptr;
     }
-    token_text_buffer& operator=(token_text_buffer&& rhs) noexcept
+    token_carry_buffer& operator=(token_carry_buffer&&) = delete;
-    {
+    ~token_carry_buffer() = default;
-        m_data = std::move(rhs.m_data);
-        m_end = rhs.m_end;
-        m_capacity_end = rhs.m_capacity_end;
-        rhs.m_end = rhs.m_capacity_end = nullptr;
-        return *this;
-    }
-    ~token_text_buffer() = default;
 
     void clear() noexcept
     {
         m_end = m_data.get();
     }
 
-    bool empty() const noexcept
+    void push_back(char c)
-    {
-        return m_end == m_data.get();
-    }
-
-    void push_back(CharType c)
     {
         if (JSON_HEDLEY_UNLIKELY(m_end == m_capacity_end))
         {
-            make_room(1);
+            grow(1);
         }
         *m_end++ = c;
     }
 
-    /// drop the last character
+    void append(const char* first, const char* last)
-    void pop_back() noexcept
-    {
-        JSON_ASSERT(!empty());
-        --m_end;
-    }
-
-    void append(const CharType* first, const CharType* last)
     {
         const auto n = static_cast<std::size_t>(last - first);
         const auto room = static_cast<std::size_t>(m_capacity_end - m_end);
-        if (JSON_HEDLEY_UNLIKELY(n > room))
+        if (n > room)
         {
-            append_long(first, n);
+            grow(n);
-            return;
         }
         if (n != 0)
         {
-            std::memcpy(m_end, first, n * sizeof(CharType));
+            std::memcpy(m_end, first, n);
         }
         m_end += n;
     }
 
     /// replace the contents of @a out
-    void copy_to(std::vector<CharType>& out) const
+    void copy_to(std::vector<char>& out) const
     {
         out.assign(m_data.get(), m_end);
     }
 
   private:
-    /// append @a n characters that do not fit, in pieces of at most tail()
+    /// make room for @a extra more characters
-    /// characters, so that dropping the middle keeps the last tail() of them
+    JSON_HEDLEY_NEVER_INLINE void grow(std::size_t extra)
-    JSON_HEDLEY_NEVER_INLINE void append_long(const CharType* first, std::size_t n)
     {
-        while (n != 0)
+        const auto size = static_cast<std::size_t>(m_end - m_data.get());
+        const auto capacity = static_cast<std::size_t>(m_capacity_end - m_data.get());
+        const std::size_t new_capacity = (std::max)(capacity < 32 ? static_cast<std::size_t>(32) : 2 * capacity, size + extra);
+        std::unique_ptr<char[]> data(new char[new_capacity]); // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
+        if (size != 0)
         {
-            const std::size_t piece = n < tail() ? n : tail();
+            std::memcpy(data.get(), m_data.get(), size);
-            make_room(piece);
-            std::memcpy(m_end, first, piece * sizeof(CharType));
-            m_end += piece;
-            first += piece;
-            n -= piece;
         }
+        m_data = std::move(data);
+        m_end = m_data.get() + size;
+        m_capacity_end = m_data.get() + new_capacity;
     }
 
-    /// make room for @a extra (at most tail()) more characters: drop the
+    std::unique_ptr<char[]> m_data{}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays,readability-redundant-member-init)
-    /// middle of a long token instead of growing beyond limit()
+    char* m_end = nullptr;
-    JSON_HEDLEY_NEVER_INLINE void make_room(std::size_t extra)
+    char* m_capacity_end = nullptr;
-    {
-        // nothing is allocated before the first character
-        std::size_t size = m_data ? static_cast<std::size_t>(m_end - m_data.get()) : 0;
-        if (size + extra > limit() && size > head() + tail())
-        {
-            std::memmove(m_data.get() + head(), m_end - tail(), tail() * sizeof(CharType));
-            m_end = m_data.get() + head() + tail();
-            size = head() + tail();
-        }
-        const std::size_t capacity = m_data ? static_cast<std::size_t>(m_capacity_end - m_data.get()) : 0;
-        if (size + extra > capacity)
-        {
-            // never more than limit(): from there on, the middle is dropped
-            const std::size_t doubled = capacity < 32 ? static_cast<std::size_t>(32) : 2 * capacity;
-            const std::size_t new_capacity = (std::max)(doubled < limit() ? doubled : limit(), size + extra);
-            std::unique_ptr<CharType[]> data(new CharType[new_capacity]); // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
-            if (size != 0)
-            {
-                std::memcpy(data.get(), m_data.get(), size * sizeof(CharType));
-            }
-            m_data = std::move(data);
-            m_end = m_data.get() + size;
-            m_capacity_end = m_data.get() + new_capacity;
-        }
-    }
-
-    std::unique_ptr<CharType[]> m_data{}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays,readability-redundant-member-init)
-    CharType* m_end = nullptr;
-    CharType* m_capacity_end = nullptr;
 };
-
-/// the part of a token that an input adapter copied out of its window
-using token_carry_buffer = token_text_buffer<char>;
-
-////////////////////
-// input adapters //
-////////////////////
-
-#ifndef JSON_NO_IO
 /*!
 Input adapter for stdio file access. The file is locked for the lifetime of the
 adapter and read with the unlocked stdio functions (see

include/nlohmann/detail/input/lexer.hpp

@@ -494,10 +494,7 @@ class lexer : public lexer_base<BasicJsonType>
     /// streaming adapter: capture the characters
     void bulk_track_token(const char* data, std::size_t n, std::false_type /*lazy*/)
     {
-        for (std::size_t i = 0; i < n; ++i)
+        token_string.insert(token_string.end(), data, data + n);
-        {
-            token_string.push_back(static_cast<char_type>(data[i]));
-        }
     }
 
     /// streaming input: no bulk fast path
@@ -2240,28 +2237,15 @@ scan_number_done:
         const std::size_t stop = ia.get_consumed_count() - (pending_real_unget ? 1u : 0u);
         if (JSON_HEDLEY_LIKELY(stop >= token_string_start))
         {
-            // only the beginning and the end of a long token are shown (see
+            ia.copy_consumed_range(token_string_start, stop, out);
-            // get_token_string), so copy only these
-            constexpr std::size_t head = token_text_buffer<char_type>::head();
-            constexpr std::size_t tail = token_text_buffer<char_type>::tail();
-            if (stop - token_string_start > head + tail)
-            {
-                ia.copy_consumed_range(token_string_start, token_string_start + head, out);
-                ia.copy_consumed_range(stop - tail, stop, out);
-            }
-            else
-            {
-                ia.copy_consumed_range(token_string_start, stop, out);
-            }
         }
         return out;
     }
 
     /// streaming adapter: the token was copied eagerly while scanning
-    const std::vector<char_type>& collect_token_chars(std::vector<char_type>& out, std::false_type /*lazy*/) const
+    const std::vector<char_type>& collect_token_chars(std::vector<char_type>& /*out*/, std::false_type /*lazy*/) const
     {
-        token_string.copy_to(out);
+        return token_string;
-        return out;
     }
 
     /// return the last read token (for errors only).  Will never contain EOF
@@ -2272,32 +2256,10 @@ scan_number_done:
         std::vector<char_type> reconstructed;
         const std::vector<char_type>& chars = collect_token_chars(reconstructed, std::integral_constant<bool, lazy_token_string> {});
 
-        // a long token is shown by its first and its last head() characters;
+        // escape control characters
-        // the buffers that keep it while it is read keep no more than these
-        // and a few more (see token_text_buffer)
-        constexpr std::size_t shown = token_text_buffer<char_type>::head();
         std::string result;
-        if (chars.size() > 2 * shown)
+        for (const auto c : chars)
         {
-            append_escaped(result, chars.begin(), chars.begin() + static_cast<std::ptrdiff_t>(shown));
-            result += "...";
-            append_escaped(result, chars.end() - static_cast<std::ptrdiff_t>(shown), chars.end());
-        }
-        else
-        {
-            append_escaped(result, chars.begin(), chars.end());
-        }
-        return result;
-    }
-
-  private:
-    /// append the characters [first, last) to @a result, escaping control characters
-    template<typename Iterator>
-    static void append_escaped(std::string& result, Iterator first, Iterator last)
-    {
-        for (; first != last; ++first)
-        {
-            const auto c = *first;
             if (static_cast<unsigned char>(c) <= '\x1F')
             {
                 // escape control characters
@@ -2311,9 +2273,9 @@ scan_number_done:
                 result.push_back(static_cast<std::string::value_type>(c));
             }
         }
-    }
 
-  public:
+        return result;
+    }
 
     /// return syntax error message
     JSON_HEDLEY_RETURNS_NON_NULL
@@ -2563,7 +2525,7 @@ scan_number_done:
 
     /// raw input token string for error messages; only populated for streaming
     /// adapters (seekable adapters reconstruct it lazily via token_string_start)
-    token_text_buffer<char_type> token_string {};
+    std::vector<char_type> token_string {};
 
     /// start offset of the current token within the input, used to reconstruct
     /// the last read token on error for seekable adapters (see collect_token_chars)

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,355 @@ 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
@@ -1052,7 +1268,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;
             }
@@ -2095,6 +2311,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)
         {
@@ -2186,7 +2403,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
@@ -2238,6 +2455,19 @@ 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

@@ -9323,164 +9323,87 @@ inline const char* empty_input_message() noexcept
     return "attempting to parse an empty input; check that your input string or stream contains the expected JSON";
 }
 
+////////////////////
+// input adapters //
+////////////////////
+
+#ifndef JSON_NO_IO
 /*!
-@brief the characters of the last read token, kept for error messages
-
 A growable array of characters for the part of a token that an input adapter
-copied out of its window, or that the lexer copies while it scans input it
+copied out of its window: unlike std::vector<char>::push_back(), appending a
-cannot read again: unlike std::vector::push_back(), appending a character
+character takes no reference to a local, and is a few instructions when there
-takes no reference to a local, and is a few instructions when there is room.
+is room.
-
-The token is only needed for error messages, which show its first head()
-characters and its last head() characters (see lexer::get_token_string). The
-buffer therefore keeps the first head() and at least the last tail()
-characters: when it is full and holds more than limit() characters, it drops
-the characters in between instead of growing. That happens where it would
-otherwise reallocate, so appending stays as cheap as before, and a long string
-or a long run of whitespace read from a stream is not kept a second time.
 */
-template<typename CharType>
+class token_carry_buffer
-class token_text_buffer
 {
   public:
-    static constexpr std::size_t head() noexcept
+    token_carry_buffer() = default;
-    {
+    token_carry_buffer(const token_carry_buffer&) = delete;
-        return 4096;
+    token_carry_buffer& operator=(const token_carry_buffer&) = delete;
-    }
+    token_carry_buffer(token_carry_buffer&& rhs) noexcept
-    /// a little more than head(), as the last character may be handed back
-    static constexpr std::size_t tail() noexcept
-    {
-        return head() + 16;
-    }
-    static constexpr std::size_t limit() noexcept
-    {
-        return head() + (2 * tail());
-    }
-
-    token_text_buffer() = default;
-    token_text_buffer(const token_text_buffer&) = delete;
-    token_text_buffer& operator=(const token_text_buffer&) = delete;
-    token_text_buffer(token_text_buffer&& rhs) noexcept
         : m_data(std::move(rhs.m_data)), m_end(rhs.m_end), m_capacity_end(rhs.m_capacity_end)
     {
         rhs.m_end = rhs.m_capacity_end = nullptr;
     }
-    token_text_buffer& operator=(token_text_buffer&& rhs) noexcept
+    token_carry_buffer& operator=(token_carry_buffer&&) = delete;
-    {
+    ~token_carry_buffer() = default;
-        m_data = std::move(rhs.m_data);
-        m_end = rhs.m_end;
-        m_capacity_end = rhs.m_capacity_end;
-        rhs.m_end = rhs.m_capacity_end = nullptr;
-        return *this;
-    }
-    ~token_text_buffer() = default;
 
     void clear() noexcept
     {
         m_end = m_data.get();
     }
 
-    bool empty() const noexcept
+    void push_back(char c)
-    {
-        return m_end == m_data.get();
-    }
-
-    void push_back(CharType c)
     {
         if (JSON_HEDLEY_UNLIKELY(m_end == m_capacity_end))
         {
-            make_room(1);
+            grow(1);
         }
         *m_end++ = c;
     }
 
-    /// drop the last character
+    void append(const char* first, const char* last)
-    void pop_back() noexcept
-    {
-        JSON_ASSERT(!empty());
-        --m_end;
-    }
-
-    void append(const CharType* first, const CharType* last)
     {
         const auto n = static_cast<std::size_t>(last - first);
         const auto room = static_cast<std::size_t>(m_capacity_end - m_end);
-        if (JSON_HEDLEY_UNLIKELY(n > room))
+        if (n > room)
         {
-            append_long(first, n);
+            grow(n);
-            return;
         }
         if (n != 0)
         {
-            std::memcpy(m_end, first, n * sizeof(CharType));
+            std::memcpy(m_end, first, n);
         }
         m_end += n;
     }
 
     /// replace the contents of @a out
-    void copy_to(std::vector<CharType>& out) const
+    void copy_to(std::vector<char>& out) const
     {
         out.assign(m_data.get(), m_end);
     }
 
   private:
-    /// append @a n characters that do not fit, in pieces of at most tail()
+    /// make room for @a extra more characters
-    /// characters, so that dropping the middle keeps the last tail() of them
+    JSON_HEDLEY_NEVER_INLINE void grow(std::size_t extra)
-    JSON_HEDLEY_NEVER_INLINE void append_long(const CharType* first, std::size_t n)
     {
-        while (n != 0)
+        const auto size = static_cast<std::size_t>(m_end - m_data.get());
+        const auto capacity = static_cast<std::size_t>(m_capacity_end - m_data.get());
+        const std::size_t new_capacity = (std::max)(capacity < 32 ? static_cast<std::size_t>(32) : 2 * capacity, size + extra);
+        std::unique_ptr<char[]> data(new char[new_capacity]); // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
+        if (size != 0)
         {
-            const std::size_t piece = n < tail() ? n : tail();
+            std::memcpy(data.get(), m_data.get(), size);
-            make_room(piece);
-            std::memcpy(m_end, first, piece * sizeof(CharType));
-            m_end += piece;
-            first += piece;
-            n -= piece;
         }
+        m_data = std::move(data);
+        m_end = m_data.get() + size;
+        m_capacity_end = m_data.get() + new_capacity;
     }
 
-    /// make room for @a extra (at most tail()) more characters: drop the
+    std::unique_ptr<char[]> m_data{}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays,readability-redundant-member-init)
-    /// middle of a long token instead of growing beyond limit()
+    char* m_end = nullptr;
-    JSON_HEDLEY_NEVER_INLINE void make_room(std::size_t extra)
+    char* m_capacity_end = nullptr;
-    {
-        // nothing is allocated before the first character
-        std::size_t size = m_data ? static_cast<std::size_t>(m_end - m_data.get()) : 0;
-        if (size + extra > limit() && size > head() + tail())
-        {
-            std::memmove(m_data.get() + head(), m_end - tail(), tail() * sizeof(CharType));
-            m_end = m_data.get() + head() + tail();
-            size = head() + tail();
-        }
-        const std::size_t capacity = m_data ? static_cast<std::size_t>(m_capacity_end - m_data.get()) : 0;
-        if (size + extra > capacity)
-        {
-            // never more than limit(): from there on, the middle is dropped
-            const std::size_t doubled = capacity < 32 ? static_cast<std::size_t>(32) : 2 * capacity;
-            const std::size_t new_capacity = (std::max)(doubled < limit() ? doubled : limit(), size + extra);
-            std::unique_ptr<CharType[]> data(new CharType[new_capacity]); // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
-            if (size != 0)
-            {
-                std::memcpy(data.get(), m_data.get(), size * sizeof(CharType));
-            }
-            m_data = std::move(data);
-            m_end = m_data.get() + size;
-            m_capacity_end = m_data.get() + new_capacity;
-        }
-    }
-
-    std::unique_ptr<CharType[]> m_data{}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays,readability-redundant-member-init)
-    CharType* m_end = nullptr;
-    CharType* m_capacity_end = nullptr;
 };
-
-/// the part of a token that an input adapter copied out of its window
-using token_carry_buffer = token_text_buffer<char>;
-
-////////////////////
-// input adapters //
-////////////////////
-
-#ifndef JSON_NO_IO
 /*!
 Input adapter for stdio file access. The file is locked for the lifetime of the
 adapter and read with the unlocked stdio functions (see
@@ -13975,10 +13898,7 @@ class lexer : public lexer_base<BasicJsonType>
     /// streaming adapter: capture the characters
     void bulk_track_token(const char* data, std::size_t n, std::false_type /*lazy*/)
     {
-        for (std::size_t i = 0; i < n; ++i)
+        token_string.insert(token_string.end(), data, data + n);
-        {
-            token_string.push_back(static_cast<char_type>(data[i]));
-        }
     }
 
     /// streaming input: no bulk fast path
@@ -15721,28 +15641,15 @@ scan_number_done:
         const std::size_t stop = ia.get_consumed_count() - (pending_real_unget ? 1u : 0u);
         if (JSON_HEDLEY_LIKELY(stop >= token_string_start))
         {
-            // only the beginning and the end of a long token are shown (see
+            ia.copy_consumed_range(token_string_start, stop, out);
-            // get_token_string), so copy only these
-            constexpr std::size_t head = token_text_buffer<char_type>::head();
-            constexpr std::size_t tail = token_text_buffer<char_type>::tail();
-            if (stop - token_string_start > head + tail)
-            {
-                ia.copy_consumed_range(token_string_start, token_string_start + head, out);
-                ia.copy_consumed_range(stop - tail, stop, out);
-            }
-            else
-            {
-                ia.copy_consumed_range(token_string_start, stop, out);
-            }
         }
         return out;
     }
 
     /// streaming adapter: the token was copied eagerly while scanning
-    const std::vector<char_type>& collect_token_chars(std::vector<char_type>& out, std::false_type /*lazy*/) const
+    const std::vector<char_type>& collect_token_chars(std::vector<char_type>& /*out*/, std::false_type /*lazy*/) const
     {
-        token_string.copy_to(out);
+        return token_string;
-        return out;
     }
 
     /// return the last read token (for errors only).  Will never contain EOF
@@ -15753,32 +15660,10 @@ scan_number_done:
         std::vector<char_type> reconstructed;
         const std::vector<char_type>& chars = collect_token_chars(reconstructed, std::integral_constant<bool, lazy_token_string> {});
 
-        // a long token is shown by its first and its last head() characters;
+        // escape control characters
-        // the buffers that keep it while it is read keep no more than these
-        // and a few more (see token_text_buffer)
-        constexpr std::size_t shown = token_text_buffer<char_type>::head();
         std::string result;
-        if (chars.size() > 2 * shown)
+        for (const auto c : chars)
         {
-            append_escaped(result, chars.begin(), chars.begin() + static_cast<std::ptrdiff_t>(shown));
-            result += "...";
-            append_escaped(result, chars.end() - static_cast<std::ptrdiff_t>(shown), chars.end());
-        }
-        else
-        {
-            append_escaped(result, chars.begin(), chars.end());
-        }
-        return result;
-    }
-
-  private:
-    /// append the characters [first, last) to @a result, escaping control characters
-    template<typename Iterator>
-    static void append_escaped(std::string& result, Iterator first, Iterator last)
-    {
-        for (; first != last; ++first)
-        {
-            const auto c = *first;
             if (static_cast<unsigned char>(c) <= '\x1F')
             {
                 // escape control characters
@@ -15792,9 +15677,9 @@ scan_number_done:
                 result.push_back(static_cast<std::string::value_type>(c));
             }
         }
-    }
 
-  public:
+        return result;
+    }
 
     /// return syntax error message
     JSON_HEDLEY_RETURNS_NON_NULL
@@ -16044,7 +15929,7 @@ scan_number_done:
 
     /// raw input token string for error messages; only populated for streaming
     /// adapters (seekable adapters reconstruct it lazily via token_string_start)
-    token_text_buffer<char_type> token_string {};
+    std::vector<char_type> token_string {};
 
     /// start offset of the current token within the input, used to reconstruct
     /// the last read token on error for seekable adapters (see collect_token_chars)
@@ -27254,139 +27139,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
     {
@@ -27409,6 +27161,355 @@ 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
@@ -27454,7 +27555,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;
             }
@@ -28497,6 +28598,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)
         {
@@ -28588,7 +28690,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
@@ -28640,6 +28742,19 @@ 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-class_lexer.cpp

@@ -12,7 +12,6 @@
 #include <nlohmann/json.hpp>
 using nlohmann::json;
 
-#include <algorithm> // min
 #include <array> // array
 #include <cctype> // toupper
 #include <cstdint> // uint32_t, uint64_t
@@ -2234,123 +2233,3 @@ TEST_CASE("serialization of short strings")
     CHECK(json("caf\xC3\xA9").dump() == "\"caf\xC3\xA9\"");
     CHECK(json("caf\xC3\xA9").dump(-1, ' ', true) == "\"caf\\u00e9\"");
 }
-
-TEST_CASE("token_text_buffer keeps the beginning and the end of a long token")
-{
-    using buffer_t = nlohmann::detail::token_text_buffer<char>;
-    constexpr std::size_t head = buffer_t::head();
-    constexpr std::size_t tail = buffer_t::tail();
-
-    // the characters 0, 1, ..., 250, 0, 1, ...
-    const auto at = [](std::size_t i)
-    {
-        return static_cast<char>(i % 251);
-    };
-    // whether out holds the first head and the last tail characters of a
-    // token of n characters (and maybe more characters of its middle)
-    const auto keeps_ends = [&](const std::vector<char>& out, std::size_t n)
-    {
-        if (out.size() < head + tail || out.size() > buffer_t::limit())
-        {
-            return false;
-        }
-        for (std::size_t i = 0; i < head; ++i)
-        {
-            if (out[i] != at(i))
-            {
-                return false;
-            }
-        }
-        for (std::size_t i = 0; i < tail; ++i)
-        {
-            if (out[out.size() - tail + i] != at(n - tail + i))
-            {
-                return false;
-            }
-        }
-        return true;
-    };
-
-    SECTION("a short token is kept as it is")
-    {
-        buffer_t buffer;
-        CHECK(buffer.empty());
-        for (std::size_t i = 0; i < head + tail; ++i)
-        {
-            buffer.push_back(at(i));
-        }
-        std::vector<char> out;
-        buffer.copy_to(out);
-        REQUIRE(out.size() == head + tail);
-        bool same = true;
-        for (std::size_t i = 0; i < out.size(); ++i)
-        {
-            same = same && out[i] == at(i);
-        }
-        CHECK(same);
-    }
-
-    SECTION("characters added one by one")
-    {
-        for (const std::size_t n :
-                {
-                    head + tail + 1, buffer_t::limit(), buffer_t::limit() + 1, static_cast<std::size_t>(100000)
-                })
-        {
-            CAPTURE(n)
-            buffer_t buffer;
-            for (std::size_t i = 0; i < n; ++i)
-            {
-                buffer.push_back(at(i));
-            }
-            std::vector<char> out;
-            buffer.copy_to(out);
-            CHECK(keeps_ends(out, n));
-
-            // the last character can be handed back
-            buffer.pop_back();
-            buffer.copy_to(out);
-            CHECK(keeps_ends(out, n - 1));
-        }
-    }
-
-    SECTION("characters added in pieces of different sizes")
-    {
-        std::vector<char> input(200000);
-        for (std::size_t i = 0; i < input.size(); ++i)
-        {
-            input[i] = at(i);
-        }
-        for (const std::size_t piece :
-                {
-                    static_cast<std::size_t>(1), static_cast<std::size_t>(100), tail - 1, tail, tail + 1, static_cast<std::size_t>(65536), input.size()
-                })
-        {
-            CAPTURE(piece)
-            buffer_t buffer;
-            for (std::size_t pos = 0; pos < input.size(); pos += piece)
-            {
-                const std::size_t n = (std::min)(piece, input.size() - pos);
-                buffer.append(input.data() + pos, input.data() + pos + n);
-            }
-            std::vector<char> out;
-            buffer.copy_to(out);
-            CHECK(keeps_ends(out, input.size()));
-        }
-    }
-
-    SECTION("clear starts a new token")
-    {
-        buffer_t buffer;
-        for (std::size_t i = 0; i < 100000; ++i)
-        {
-            buffer.push_back('x');
-        }
-        buffer.clear();
-        CHECK(buffer.empty());
-        buffer.push_back('a');
-        std::vector<char> out;
-        buffer.copy_to(out);
-        CHECK(out == std::vector<char> {'a'});
-    }
-}

tests/src/unit-class_parser.cpp

@@ -3269,116 +3269,3 @@ TEST_CASE("a plain function is accepted as parser callback for containers")
     CHECK((nlohmann::detail::can_compare_ne<std::string::const_iterator, std::string::const_iterator>::value));
     CHECK((nlohmann::detail::can_compare_ne<const char*, const char*>::value));
 }
-
-#if !defined(JSON_NOEXCEPTION)
-TEST_CASE("parse error message of a long token")
-{
-    // the message of a parse error shows the last read token; a long token is
-    // shown by its first and its last 4096 characters, and the message is the
-    // same for every kind of input
-    const auto message = [](const std::string & text, int kind) -> std::string
-    {
-        json _;
-        try
-        {
-            if (kind == 0)
-            {
-                _ = json::parse(text);
-            }
-            else if (kind == 1)
-            {
-                std::istringstream stream(text);
-                _ = json::parse(stream);
-            }
-            else if (kind == 2)
-            {
-                FILE* const file = std::tmpfile(); // NOLINT(cppcoreguidelines-owning-memory)
-                REQUIRE(file != nullptr);
-                CHECK(std::fwrite(text.data(), 1, text.size(), file) == text.size());
-                CHECK(std::fseek(file, 0, SEEK_SET) == 0);
-                try
-                {
-                    _ = json::parse(file);
-                }
-                catch (...)
-                {
-                    std::fclose(file); // NOLINT(cert-err33-c,cppcoreguidelines-owning-memory)
-                    throw;
-                }
-                std::fclose(file); // NOLINT(cert-err33-c,cppcoreguidelines-owning-memory)
-            }
-            else
-            {
-                const std::list<char> chars(text.begin(), text.end());
-                _ = json::parse(chars.begin(), chars.end());
-            }
-        }
-        catch (const json::parse_error& e)
-        {
-            return e.what();
-        }
-        return "no error";
-    };
-
-    SECTION("a short token is shown completely")
-    {
-        const std::string text = "[\"" + std::string(8000, 'a') + "\x01\"]";
-        const std::string expected = "last read: '\"" + std::string(8000, 'a') + "<U+0001>'";
-        for (int kind = 0; kind < 4; ++kind)
-        {
-            CAPTURE(kind)
-            const std::string m = message(text, kind);
-            CHECK(m.size() > expected.size());
-            CHECK(m.compare(m.size() - expected.size(), expected.size(), expected) == 0);
-        }
-    }
-
-    SECTION("a long string")
-    {
-        const std::string text = "[\"" + std::string(100000, 'a') + "b\x01\"]";
-        // the token is '"', 100,000 times 'a', 'b', and the control character
-        const std::string expected = "last read: '\"" + std::string(4095, 'a') + "..." + std::string(4094, 'a') + "b<U+0001>'";
-        for (int kind = 0; kind < 4; ++kind)
-        {
-            CAPTURE(kind)
-            const std::string m = message(text, kind);
-            CHECK(m.size() > expected.size());
-            CHECK(m.compare(m.size() - expected.size(), expected.size(), expected) == 0);
-        }
-    }
-
-    SECTION("a long run of whitespace after a number")
-    {
-        // the token begins with the number and ends with the invalid character
-        const std::string text = "[1," + std::string(100000, '\n') + "?]";
-        std::string expected = "last read: '1,";
-        for (int i = 0; i < 4094; ++i)
-        {
-            expected += "<U+000A>";
-        }
-        expected += "...";
-        for (int i = 0; i < 4095; ++i)
-        {
-            expected += "<U+000A>";
-        }
-        expected += "?'";
-        for (int kind = 0; kind < 4; ++kind)
-        {
-            CAPTURE(kind)
-            const std::string m = message(text, kind);
-            CHECK(m.size() > expected.size());
-            CHECK(m.compare(m.size() - expected.size(), expected.size(), expected) == 0);
-        }
-    }
-
-    SECTION("valid input with a long run of whitespace")
-    {
-        const std::string text = "1" + std::string(100000, ' ');
-        for (int kind = 0; kind < 4; ++kind)
-        {
-            CAPTURE(kind)
-            CHECK(message(text, kind) == "no error");
-        }
-    }
-}
-#endif

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>
@@ -1238,6 +1240,34 @@ 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")
     {
@@ -1560,3 +1590,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());
+    }
+}