Merge branch 'develop' into copy-scratch-allocator

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

.github/workflows/codeql-analysis.yml

@@ -38,14 +38,14 @@ jobs:
 
     # Initializes the CodeQL tools for scanning.
     - name: Initialize CodeQL
-      uses: github/codeql-action/init@1c5b675653bb5c22dbe9b12b556ec555138e09fd # v4.38.1
+      uses: github/codeql-action/init@b96794f015dfd88f77b49b1c93e0fa7110f94c63 # v4.38.0
       with:
         languages: c-cpp
 
     # Autobuild attempts to build any compiled languages  (C/C++, C#, or Java).
     # If this step fails, then you should remove it and run the build manually (see below)
     - name: Autobuild
-      uses: github/codeql-action/autobuild@1c5b675653bb5c22dbe9b12b556ec555138e09fd # v4.38.1
+      uses: github/codeql-action/autobuild@b96794f015dfd88f77b49b1c93e0fa7110f94c63 # v4.38.0
 
     - name: Perform CodeQL Analysis
-      uses: github/codeql-action/analyze@1c5b675653bb5c22dbe9b12b556ec555138e09fd # v4.38.1
+      uses: github/codeql-action/analyze@b96794f015dfd88f77b49b1c93e0fa7110f94c63 # v4.38.0

.github/workflows/flawfinder.yml

@@ -43,6 +43,6 @@ jobs:
           output: 'flawfinder_results.sarif'
 
       - name: Upload analysis results to GitHub Security tab
-        uses: github/codeql-action/upload-sarif@1c5b675653bb5c22dbe9b12b556ec555138e09fd # v4.38.1
+        uses: github/codeql-action/upload-sarif@b96794f015dfd88f77b49b1c93e0fa7110f94c63 # v4.38.0
         with:
           sarif_file: ${{github.workspace}}/flawfinder_results.sarif

.github/workflows/scorecards.yml

@@ -76,6 +76,6 @@ jobs:
 
       # Upload the results to GitHub's code scanning dashboard.
       - name: "Upload to code-scanning"
-        uses: github/codeql-action/upload-sarif@1c5b675653bb5c22dbe9b12b556ec555138e09fd # v4.38.1
+        uses: github/codeql-action/upload-sarif@b96794f015dfd88f77b49b1c93e0fa7110f94c63 # v4.38.0
         with:
           sarif_file: results.sarif

.github/workflows/semgrep.yml

@@ -61,7 +61,7 @@ jobs:
 
       # Upload SARIF file generated in previous step
       - name: Upload SARIF file
-        uses: github/codeql-action/upload-sarif@1c5b675653bb5c22dbe9b12b556ec555138e09fd # v4.38.1
+        uses: github/codeql-action/upload-sarif@b96794f015dfd88f77b49b1c93e0fa7110f94c63 # v4.38.0
         with:
           sarif_file: semgrep.sarif
         if: always()

docs/mkdocs/docs/features/types/template_parameters.md

@@ -562,7 +562,11 @@ binary32 or binary64 field and have no encoding for `#!cpp long double`.
 ## `AllocatorType`
 
 `AllocatorType` is instantiated with **one** argument, for each of `object_t`, `array_t`, `string_t`, `binary_t`,
-`basic_json`, and `#!cpp std::pair<const StringType, basic_json>`.
+`basic_json`, `#!cpp std::pair<const StringType, basic_json>`, and `#!cpp std::pair<StringType, basic_json>`.
+
+`AllocatorType` is not the only allocator a `basic_json` uses. It allocates the JSON values themselves, but most
+temporary storage is allocated with `#!cpp std::allocator`. This includes the parser's stacks and the stacks that
+process deeply nested values without recursion.
 
 ### Always required
 

include/nlohmann/json.hpp

@@ -1003,7 +1003,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     using copy_worklist_t = std::vector<std::pair<const basic_json*, basic_json*>>;
 
     /// scratch space to build the key skeleton of an object copy in one go
-    using copy_scratch_t = std::vector<std::pair<typename object_t::key_type, basic_json>>;
+    using copy_scratch_value_t = std::pair<typename object_t::key_type, basic_json>;
+    using copy_scratch_t = std::vector<copy_scratch_value_t, AllocatorType<copy_scratch_value_t>>;
 
     /// @brief copy everything of @a src into @a dst but its type and value
     static void copy_metadata(const basic_json& src, basic_json& dst)

single_include/nlohmann/json.hpp

@@ -25648,7 +25648,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     using copy_worklist_t = std::vector<std::pair<const basic_json*, basic_json*>>;
 
     /// scratch space to build the key skeleton of an object copy in one go
-    using copy_scratch_t = std::vector<std::pair<typename object_t::key_type, basic_json>>;
+    using copy_scratch_value_t = std::pair<typename object_t::key_type, basic_json>;
+    using copy_scratch_t = std::vector<copy_scratch_value_t, AllocatorType<copy_scratch_value_t>>;
 
     /// @brief copy everything of @a src into @a dst but its type and value
     static void copy_metadata(const basic_json& src, basic_json& dst)

tests/src/unit-allocator.cpp

@@ -270,6 +270,82 @@ TEST_CASE("controlled bad_alloc")
     }
 }
 
+namespace
+{
+// counts the allocations of pairs with a non-const first member: the object
+// types store std::pair<const Key, T>, so only the scratch space of the
+// iterative deep copy allocates std::pair<Key, T>
+std::size_t scratch_pair_allocations = 0;
+
+template<class T>
+struct is_scratch_pair : std::false_type {};
+
+template<class K, class V>
+struct is_scratch_pair<std::pair<K, V>> : std::integral_constant < bool, !std::is_const<K>::value > {};
+
+template<class T>
+struct scratch_counting_allocator : std::allocator<T>
+{
+    using std::allocator<T>::allocator;
+
+    T* allocate(std::size_t n)
+    {
+        if (is_scratch_pair<T>::value)
+        {
+            ++scratch_pair_allocations;
+        }
+        return std::allocator<T>::allocate(n);
+    }
+
+#ifdef __cpp_lib_allocate_at_least
+    // std::allocator<T>::allocate_at_least would bypass the counting, and
+    // libc++'s containers prefer it over allocate from C++23 on
+    auto allocate_at_least(std::size_t n)
+    {
+        if (is_scratch_pair<T>::value)
+        {
+            ++scratch_pair_allocations;
+        }
+        return std::allocator<T>::allocate_at_least(n);
+    }
+#endif
+
+    template <class U>
+    struct rebind
+    {
+        using other = scratch_counting_allocator<U>;
+    };
+};
+} // namespace
+
+TEST_CASE("deep copy uses the provided allocator")
+{
+    using counting_json = nlohmann::basic_json<std::map,
+          std::vector,
+          std::string,
+          bool,
+          std::int64_t,
+          std::uint64_t,
+          double,
+          scratch_counting_allocator>;
+
+    // deeper than the 128 levels the copy constructor descends into, so the
+    // innermost objects are copied by the iterative deep copy
+    counting_json j = 1;
+    for (std::size_t i = 0; i < 300; ++i)
+    {
+        counting_json wrapper = counting_json::object();
+        wrapper["a"] = std::move(j);
+        j = std::move(wrapper);
+    }
+
+    scratch_pair_allocations = 0;
+    // NOLINTNEXTLINE(performance-unnecessary-copy-initialization): the copy is what is tested
+    const counting_json copy(j);
+    CHECK(scratch_pair_allocations > 0);
+    CHECK(copy == j);
+}
+
 namespace
 {
 template<class T>