Bump lukka/get-cmake from 4.4.5 to 4.5.0

get-cmake 4.4.5 does not know CMake 4.5.0, so the ci_module_cpp20 jobs
that request '^4.5.0' failed in the setup step. Bump every pin so all
jobs use the same action version.

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

.github/workflows/ubuntu.yml

@@ -25,7 +25,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -38,7 +38,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Check that Meson and pkg-config offer the CMake options
         run: make check_build_options
       - name: Install Meson
@@ -92,7 +92,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -123,7 +123,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -142,7 +142,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -168,7 +168,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -244,7 +244,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: CXX=g++-${{ matrix.compiler }} cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -262,7 +262,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -279,7 +279,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Disable filesystem support (std::filesystem is unusable) for clang 7 / 8 / 9 / 10
         run: echo "JSON_FORCED_GLOBAL_COMPILE_OPTIONS=-DJSON_HAS_FILESYSTEM=0;-DJSON_HAS_EXPERIMENTAL_FILESYSTEM=0" >> "$GITHUB_ENV"
         if: ${{ matrix.compiler == '7' || matrix.compiler == '8' || matrix.compiler == '9' || matrix.compiler == '10' }}
@@ -299,7 +299,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -319,7 +319,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build with libc++
@@ -346,7 +346,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -362,13 +362,11 @@ jobs:
       - uses: actions/checkout@3d3c42e5aac5ba805825da76410c181273ba90b1 # v7.0.1
         with:
           persist-credentials: false
-      # The module test uses `import std;`, which needs CMake's experimental
-      # import-std support. Its opt-in token is CMake-version-specific, so pin
-      # CMake to the version whose token is set in tests/module_cpp20/CMakeLists.txt.
-      - name: Get pinned CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+      # The module test uses `import std;`, which needs CMake 4.5 or newer.
+      - name: Get CMake 4.5+ and ninja
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
         with:
-          cmakeVersion: 4.3.4
+          cmakeVersion: '^4.5.0'
       # Clang: the std library module is provided by libc++ (the image's libstdc++
       # ships none), and the image's libc++ module manifest has a broken relative
       # path — repoint it at the real module sources.
@@ -392,7 +390,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -409,7 +407,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -423,7 +421,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DJSON_CI=On
       - name: Build
@@ -443,7 +441,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Run CMake
         run: cmake -S . -B build -DCMAKE_TOOLCHAIN_FILE=$EMSDK/upstream/emscripten/cmake/Modules/Platform/Emscripten.cmake -GNinja
       - name: Build
@@ -484,7 +482,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Check that the job runs natively on arm64
         run: uname -m && test "$(uname -m)" = aarch64
       - name: Run CMake

.github/workflows/windows.yml

@@ -90,7 +90,7 @@ jobs:
         with:
           persist-credentials: false
       - name: Get latest CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
       - name: Set extra CXX_FLAGS for latest std_version
         # /wd5285 silences C5285 emitted by the bundled third-party doctest.h, which
         # specializes std::tuple (newly diagnosed by the VS2026 v145 toolset)
@@ -212,13 +212,11 @@ jobs:
       - uses: actions/checkout@3d3c42e5aac5ba805825da76410c181273ba90b1 # v7.0.1
         with:
           persist-credentials: false
-      # The module test uses `import std;`, which needs CMake's experimental
-      # import-std support. Its opt-in token is CMake-version-specific, so pin
-      # CMake to the version whose token is set in tests/module_cpp20/CMakeLists.txt.
-      - name: Get pinned CMake and ninja
-        uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
+      # The module test uses `import std;`, which needs CMake 4.5 or newer.
+      - name: Get CMake 4.5+ and ninja
+        uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
         with:
-          cmakeVersion: 4.3.4
+          cmakeVersion: '^4.5.0'
       # CMAKE_CXX_FLAGS replaces CMake's MSVC defaults (which include /EHsc), and
       # ci_module_cpp20 forwards it to the module build, so list /EHsc explicitly
       - name: Run CMake (Debug)

README.md

@@ -165,7 +165,8 @@ std::ifstream f("example.json");
 json data = json::parse(f);
 ```
 
-If using modules (enabled with `NLOHMANN_JSON_BUILD_MODULES`), this example becomes:
+If using modules (enabled with `NLOHMANN_JSON_BUILD_MODULES`; `import std;` needs CMake 4.5 or newer, see the
+[modules documentation](https://json.nlohmann.me/features/modules/)), this example becomes:
 ```cpp
 import std;
 import nlohmann.json;

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/modules.md

@@ -9,7 +9,19 @@ Importing the module instead of including the header reduces the compile time of
 ## Requirements
 The `nlohmann.json` module requires that the build system is configured to build and resolve modules when imported. Obviously, as modules were introduced in C++20, this feature can only be used in C++20 and subsequent versions.
 
-To enable building the `nlohmann.json` module (which is not done by default), the macro `NLOHMANN_JSON_BUILD_MODULES` must be passed to the build system.
+To enable building the `nlohmann.json` module (which is not done by default), set the CMake option
+[`NLOHMANN_JSON_BUILD_MODULES`](../integration/cmake.md#nlohmann_json_build_modules) and link the
+`nlohmann_json_modules` target.
+
+With CMake, building the module needs:
+
+- CMake 3.28 or newer, and
+- a generator that scans for modules: Ninja (1.11 or newer), Ninja Multi-Config, or Visual Studio 2022 or newer.
+
+The example below also uses `import std;`. CMake supports it without experimental opt-in since version 4.5, and then
+only with the Ninja generators and these toolchains: Clang 18.1.2 or newer (with libc++ or libstdc++), MSVC toolset 14.36
+(Visual Studio 17.6) or newer, and GCC 15 or newer (GCC 16 on macOS). With older CMake versions, `import std;` needs
+CMake's version-specific experimental opt-in.
 
 ## Example
 When using modules rather than headers, the previous example for creating a `json` object through a JSON file, would instead be:
@@ -67,7 +79,7 @@ and should not be used directly:
 
 ## Known issues
 
-C++20 modules support is exercised in CI against current GCC and Clang on Ubuntu, and the default MSVC toolset on Windows Server 2022 — there is no documented minimum compiler version, unlike feature-test-macro-gated features such as [`JSON_HAS_RANGES`](../api/macros/json_has_ranges.md).
+C++20 modules support is exercised in CI with CMake 4.5 and `import std;` against current GCC and Clang on Ubuntu, and the default MSVC toolset on Windows Server 2022 — there is no documented minimum compiler version, unlike feature-test-macro-gated features such as [`JSON_HAS_RANGES`](../api/macros/json_has_ranges.md).
 
 !!! info "Known compiler issues"
 

docs/mkdocs/docs/integration/cmake.md

@@ -269,6 +269,9 @@ target_link_libraries(myproject PRIVATE nlohmann_json_modules)
 target_compile_definitions(myproject PRIVATE NLOHMANN_JSON_BUILD_MODULES)
 ```
 
+If `main.cpp` also uses `import std;`, the project needs CMake 4.5 or newer and a Ninja generator; see
+[Modules](../features/modules.md#requirements) for the supported toolchains.
+
 ## See also
 
 - [Macros](../api/macros/index.md) - reference of all macros

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

@@ -27139,6 +27139,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 +27294,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 +27339,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 +28382,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 +28473,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 +28525,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/module_cpp20/CMakeLists.txt

@@ -1,11 +1,6 @@
-cmake_minimum_required(VERSION 3.30)
-
-# `import std;` (used by main.cpp) needs CMake's experimental C++ import-std
-# support. The accepted token is CMake-version-specific; this value matches the
-# CMake version pinned in the ci_module_cpp20 CI jobs (4.3.x). If that pin is
-# bumped, this token must be updated to match (configuration fails loudly
-# otherwise).
-set(CMAKE_EXPERIMENTAL_CXX_IMPORT_STD "451f2fe2-a8a2-47c3-bc32-94786d8fc91b")
+# `import std;` (used by main.cpp) is supported without experimental opt-in
+# since CMake 4.5: it is available to every target that scans for C++ modules.
+cmake_minimum_required(VERSION 4.5)
 
 project(json_test CXX)
 
@@ -13,7 +8,6 @@ project(json_test CXX)
 set(CMAKE_CXX_STANDARD 23)
 set(CMAKE_CXX_STANDARD_REQUIRED ON)
 set(CMAKE_CXX_EXTENSIONS OFF)
-set(CMAKE_CXX_MODULE_STD ON)
 
 set(NLOHMANN_JSON_BUILD_MODULES ON CACHE BOOL "Enable nlohmann.json module support")
 

tests/module_cpp20/main.cpp

@@ -17,8 +17,8 @@ using namespace nlohmann::literals;
 // Standard-library facilities are pulled in via `import std;` rather than
 // textual `#include`s: mixing `import` with textual standard headers does not
 // compile under GCC's C++20 modules implementation, whereas `import std;` works
-// across GCC, Clang, and MSVC. This requires C++23 and CMake's (experimental)
-// import-std support; see CMakeLists.txt.
+// across GCC, Clang, and MSVC. This requires C++23 and CMake 4.5 or newer;
+// see CMakeLists.txt.
 int main()
 {
     // basic_json / json: parsing and value access

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());
-    }
-}