Compare commits

..
Author SHA1 Message Date
Niels Lohmann 766ca3164d Merge fix/ubjson-valueless-budget into fix/reserve-unbacked-count
The FILE* test that the merged commit changes was moved to
unit-ubjson_valueless.cpp here and does not use rewind(); keep this side.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-13 11:37:48 +01:00
Niels Lohmann f1b26e20c6 Use fseek instead of rewind in the UBJSON FILE* test
clang-tidy (bugprone-unsafe-functions) rejects rewind() because it has no
error detection. Check the result of fseek() instead.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-13 11:37:35 +01:00
Niels Lohmann 619fafc087 Merge fix/ubjson-valueless-budget into fix/reserve-unbacked-count, wrap docs, skip ICC-incompatible tests
Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-13 07:35:11 +01:00
Niels Lohmann a2cc727dd5 Merge develop into fix/ubjson-valueless-budget and avoid MSVC C4127
Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-13 07:33:26 +01:00
Niels Lohmann 75e7198260 Merge branch 'fix/ubjson-valueless-budget' into fix/reserve-unbacked-count
Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-11 22:45:07 +01:00
Niels Lohmann 73aea7ce54 Add JSON_UBJSON_VALUELESS_ELEMENTS_PER_BYTE to set the UBJSON whole-input budget (#6083)
* Add JSON_UBJSON_VALUELESS_ELEMENTS_PER_BYTE to set the UBJSON whole-input budget

The whole-input budget for the elements of optimized UBJSON arrays of
type Z, T and F (1048576 plus 4 per byte read) rejects files written by
3.12.0 that have long arrays of these types, such as 1100 rows of 1000
nulls with a `$Z` annotation, and there was no way to read them. The
per-byte rate is now the macro JSON_UBJSON_VALUELESS_ELEMENTS_PER_BYTE.

Semantics:
- default 4, so the default build is unchanged (the generated code of
  from_ubjson is identical at -O2 up to source line numbers);
- the value must be a positive integer: 0, negative, non-integral, bool,
  character and wider-than-uintmax_t values fail to compile with a
  static_assert that names the macro;
- a value that does not fit into std::size_t is the largest size_t, so
  one spelling works for 32- and 64-bit targets;
- the limit base + rate * bytes_read saturates at the largest size_t
  instead of wrapping around, for any rate and input size; a rate of
  131072 (2^20 / 8) or more cannot be exceeded by any input (the
  shortest header of an array of more than 32767 elements is 8 bytes),
  which switches the whole-input budget off;
- the limit of one array (1048576) and the base (1048576) stay fixed
  constants, so the writer fallback still follows the base only and a
  reader with any rate reads everything the writer produces;
- the macro is not part of the ABI tag and must have the same value in
  every translation unit; it is documented that way.

The memory the arrays can take in a DOM is about 20 bytes per rate and
byte of input (measured, macOS, containers of 9 * rate elements:
25 bytes per input byte at rate 1, 81 at 4, 312 at 16, 1226 at 64, 5493
at 256) plus about 33 MB for the base. A 3.12.0 row of N values has a
header of b bytes (5 up to 255, 6 up to 32767, 8 above), so a table is
read completely if N <= rate * b, and otherwise up to
(1048576 + h * rate, h = outer header: 6, 7 or 9 bytes) / (N - rate * b) rows; 1100 rows of 1000 nulls need
a rate of 8. The new page of the macro documents the formulas, the
measurements, and two examples that are run by the documentation checks.

The tests of the budget move to tests/src/unit-ubjson_valueless.cpp, which
derives every boundary from the macro and is built with the rates 1,
1000000 and 0xFFFFFFFFFFFFFFFF in addition to the default (the last two
check that nothing is refused and that the limit does not wrap around);
they fail with the unchanged header for rate 1, 1000000 and the maximum.

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

* Refuse char8_t for JSON_UBJSON_VALUELESS_ELEMENTS_PER_BYTE and clarify its documentation

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

---------

Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-11 22:37:35 +01:00
Niels Lohmann 5187b6ecc7 Report an empty array for UBJSON [$N#<n>] instead of n elements (#6079)
* Report an empty array for UBJSON `[$N#<n>` instead of n elements

A no-op (N) is not a value, so an optimized array of type N holds no
element whatever count it declares. The reader skipped the elements but
still passed the declared count to the SAX parser: a handler was told
start_array(n) and no element followed, and the DOM parser reserved
min(n, 16384) values (256 KB) for an array that stays empty. Nine bytes
(`[$N#l 0x7FFFFFFF`) therefore committed 256 KB: 2000 of them in one
input, 18 KB, committed 512 MB of heap (capacity 163,840,000 values for
the 10000 arrays of the original probe: 2.6 GB for 70 KB of input).
Untouched pages keep the resident size small, but the commit charge and
a 32-bit address space are consumed.

The reader now announces 0 elements for an optimized array of type N.
The loop that skips the elements is unchanged (it never ran). A count
that does not fit into std::size_t is still rejected by the count
reader; a count that is too large for the array type of the DOM (before:
out_of_range.408 "excessive array size" from the DOM handler) is
accepted now, because the array is empty.

Behaviour change: sax_parse reports start_array(0) for `[$N#n` (before:
n); from_ubjson no longer throws out_of_range.408 for an N-typed array
whose count exceeds the maximum size of the array type.

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

* Clarify the reservation note for announced array counts

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

---------

Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-11 22:37:23 +01:00
Niels Lohmann 8001ed67b9 Merge branch 'fix/ubjson-noop-array-count' into fix/reserve-unbacked-count
Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-11 22:23:45 +01:00
Niels Lohmann af2e1c73c1 Clarify the reservation note for announced array counts
Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-11 19:05:09 +01:00
Niels Lohmann 4c75628374 Bound what the DOM parsers reserve for arrays that announce a size
Cause: #5476 made the DOM parsers reserve storage (up to 16384 elements)
for a counted array of CBOR, MessagePack, UBJSON and BJData when it
opens, before any input backs the count. The arrays that are open at the
same time keep their storage until the parse ends, so N nested headers
that announce 16384 elements and are never completed hold
N * 16384 * sizeof(json): 100,000 nested CBOR headers `99 40 00`
(300,000 bytes) peaked at 1.65 GiB, 3.12.0 at 12 MiB; the same for
MessagePack `DC 40 00`, UBJSON `[#I 16384` and BJData.

Fix: json_sax_dom_error_state, the base of the three DOM parsers, keeps a
credit of elements that may still be reserved: 65,536 at the start plus
2 for every byte the reader has read. An array that announces no more
than the credit left is reserved as before (one comparison and one
subtraction per counted array); a larger one is reserved what is left
and grows as its elements arrive. binary_reader tells a DOM parser (a
handler whose pointer converts to json_sax_dom_error_state*; a handler
that derives from one privately or protectedly, or any other SAX handler,
is not told anything and reserves as in the base of this change) where to
find its count of characters read for the duration of sax_parse(). An
RAII guard puts back the previous binding on every exit, also by
exception, so the parser never keeps a pointer to a reader that is gone
(unbound, only the per-array cap of 16384 applies); the public SAX
interface is unchanged, and start_array() still reports the announced number. A
bound per array by the remaining input would not help, since the same
bytes would back every open level; the bound has to be over all arrays.

The elements of an array take at least one byte of input each, so the
credit is more than honest input needs: none of the 19 inputs measured
(canada, citm_catalog, twitter, mesh, update-center, random, numbers,
animation, ik_rig, instruments, geo_response, jeopardy and 7 synthetic
ones, each as CBOR, MessagePack, UBJSON and BJData, with and without
size/type optimization) was given less than it announced. A value that
nests five or more arrays of 16384 elements, each with an array as its
first element, is the exception: the later ones grow as before.

Measurements (clang -O2, macOS arm64, peak memory footprint of
`/usr/bin/time -l`, reproducer: n nested headers):

              n = 20,000                n = 100,000
              develop   fix   3.12.0   develop    fix   3.12.0
  CBOR        338.7    5.9    8.2      1687.7    23.3   11.8   MiB
  MessagePack 338.9    6.0    7.3      1687.9    23.8   11.9   MiB
  UBJSON      339.0    7.6    8.0      1687.9    30.1   11.6   MiB
  BJData      339.0    7.3    7.9      1688.0    30.8   11.6   MiB

That is at most (65,536 + 2 per input byte) values: 1 MiB plus 32 bytes
per input byte with 16-byte values (a value is 24 bytes with
JSON_DIAGNOSTICS and up to 40 with JSON_DIAGNOSTIC_POSITIONS), as
documented in untrusted_input.md. Lower fixed caps do not get there: a
cap of 64 elements still peaks at 113 MiB (n = 100,000) and costs 4.7 %
on arrays of 300 elements (mat300.cbor) and 5.0 % on arrays of 10,000
(arrays_of_big.cbor).

Reader instructions retired (min of 7, 108 rows: 18 inputs in the 6 forms
CBOR, MessagePack, UBJSON and BJData plain and optimized; jeopardy, 46 MB,
is within 0.1 %), compared with the base of this change: -0.19 % to +0.37 % in the formats that announce
sizes (canada.cbor 81.9 M -> 82.1 M, many_small.cbor 333.5 M -> 334.2 M);
the benefit of #5476 is kept (without any reserve canada.cbor takes
116.8 M, +42.6 %, many_small.cbor +71.5 %, mat300.cbor +81.6 %). Rows of
plain UBJSON and BJData, whose arrays announce no size, move by -2.7 % to
+2.6 % without any code of theirs changing: the base alternates
between two instruction counts per process (452 M and 463 M for
many_pairs.ubjson, equal in cycles), and a struct with three unused
members added to the same class reproduces the 474 M mode.

Tests (CBOR, MessagePack, UBJSON, BJData): 200 nested headers that
announce 16384 elements peak at 52,433,600 bytes of DOM allocations on
the base and below 128 Ki values with the fix (scaled by sizeof(value),
so that it holds with the diagnostic macros) (counting allocator, no
process memory measured); an array that completes is still reserved in
one allocation; CBOR also checks that a DOM parser is not bound to a finished
parse (ASan: stack-use-after-scope without the guard), that wrappers
derived publicly (also with a parse inside the parse), privately and
protectedly compile and are bound or not as described, that an array that got less than it
announced decodes and that a SAX handler is told the announced size.
The new tests take 4.6 s under Valgrind at -O0 (gcc:12, all four files).

Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-11 17:10:37 +01:00
Niels Lohmann 44b1e7b2b9 Report an empty array for UBJSON [$N#<n> instead of n elements
A no-op (N) is not a value, so an optimized array of type N holds no
element whatever count it declares. The reader skipped the elements but
still passed the declared count to the SAX parser: a handler was told
start_array(n) and no element followed, and the DOM parser reserved
min(n, 16384) values (256 KB) for an array that stays empty. Nine bytes
(`[$N#l 0x7FFFFFFF`) therefore committed 256 KB: 2000 of them in one
input, 18 KB, committed 512 MB of heap (capacity 163,840,000 values for
the 10000 arrays of the original probe: 2.6 GB for 70 KB of input).
Untouched pages keep the resident size small, but the commit charge and
a 32-bit address space are consumed.

The reader now announces 0 elements for an optimized array of type N.
The loop that skips the elements is unchanged (it never ran). A count
that does not fit into std::size_t is still rejected by the count
reader; a count that is too large for the array type of the DOM (before:
out_of_range.408 "excessive array size" from the DOM handler) is
accepted now, because the array is empty.

Behaviour change: sax_parse reports start_array(0) for `[$N#n` (before:
n); from_ubjson no longer throws out_of_range.408 for an N-typed array
whose count exceeds the maximum size of the array type.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-11 10:46:41 +01:00
Niels Lohmann 71ec3b4306 Bound the total number of valueless UBJSON elements per input
An optimized UBJSON array of type Z, T or F has no payload, so its
declared count is not bounded by the input. The limit of 1048576 applied
to each array on its own, so 9 bytes (`[$Z#l` and a count) produced
1048576 values and every further 9 bytes another 1048576: 362 bytes
allocated 661 MB in a DOM, and a SAX handler received 1M events per 9
bytes.

The reader now adds the counts of all such arrays of one input and
rejects the input with out_of_range.408 when the sum exceeds 1048576
plus 4 for every byte read so far. The base is the per-array limit, so
an array that was accepted on its own before is still accepted at the
start of an input. These arrays add about 80 bytes of memory per input
byte (measured 77; one `Z` per byte needs 32), plus the base; the memory
of a document as a whole is not bounded by this. The check runs once per
valueless array, before its start event, with plain size_t arithmetic
that cannot overflow for a 32-bit size_t. Containers with a payload type
and objects (every member needs a key) are bounded by the input already
and are unchanged. BJData rejects these types.

to_ubjson counts the elements of the typed arrays it writes in one call
and writes an array in the unoptimized form (`[#n Z Z ...`) once it would
bring the total above 1048576, which a reader accepts at any input size.
The check is made only for a typed array of a valueless type, so BJData
and other arrays do not pay for it. Everything to_ubjson writes in
version 3.13.0 can therefore be read back.

Two consequences:
- to_ubjson output changes for values with more than 1048576 elements in
  arrays of type Z, T or F: such an array is written at one byte per
  element, e.g. 270000 rows of 100 nulls take 26.8 MB instead of 1.35 MB.
- Output of version 3.12.0 and earlier (typed arrays without such a
  total) is rejected by from_ubjson when the arrays hold more than
  1048576 elements plus 4 per byte of input. 3.12.0 writes a row of up to 255 nulls in 5 bytes (6 above
  255), so a table is rejected from 1075 rows of 1000 nulls or 209723
  rows of 25 (accepted: 1000 rows of 1000, 209000 rows of 25); rows of
  20 or fewer are never rejected.

Measured on the test data: no file of json_test_data (converted with
to_ubjson in all three modes, 846 round trips) holds an array of this
kind with more than 0.17 values per byte. All of them are read back.

Reproducer (K arrays of 1048576 nulls), Apple clang -O2:
  K=40 (362 bytes): before 41943040 values, 664 MB; after rejected, 33 MB
  K=2 (20 bytes):   before 2097152 values, 53 MB;   after rejected, 33 MB

The new tests count events with a SAX handler where they can: building
and comparing million-element values made the first version take 176 s
under Valgrind, the current one about 22 s.

Behaviour change: an input that holds more than 1048576 elements in
arrays of type Z, T or F at more than 4 per byte is now rejected.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>
2026-11-11 10:46:24 +01:00
36 changed files with 507 additions and 1938 deletions

No files matched your search

+23 -26
View File
@@ -25,7 +25,7 @@ jobs:
with:
persist-credentials: false
- name: Get latest CMake and ninja
uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- name: Run CMake
run: cmake -S . -B build -DJSON_CI=On
- name: Build
@@ -362,16 +362,13 @@ jobs:
- uses: actions/checkout@3d3c42e5aac5ba805825da76410c181273ba90b1 # v7.0.1
with:
persist-credentials: false
# get-cmake extracts the Ninja zip with the system unzip, which the Clang
# image lacks; other Clang jobs get away with it by hitting the cache.
- name: Install unzip (Clang)
if: matrix.container == 'silkeh/clang:latest'
run: apt-get update ; apt-get install -y unzip
# 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
# 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
with:
cmakeVersion: '^4.5.0'
cmakeVersion: 4.3.4
# 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.
@@ -395,7 +392,7 @@ jobs:
with:
persist-credentials: false
- name: Get latest CMake and ninja
uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- name: Run CMake
run: cmake -S . -B build -DJSON_CI=On
- name: Build
@@ -412,7 +409,7 @@ jobs:
with:
persist-credentials: false
- name: Get latest CMake and ninja
uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- name: Run CMake
run: cmake -S . -B build -DJSON_CI=On
- name: Build
@@ -426,7 +423,7 @@ jobs:
with:
persist-credentials: false
- name: Get latest CMake and ninja
uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- name: Run CMake
run: cmake -S . -B build -DJSON_CI=On
- name: Build
@@ -446,7 +443,7 @@ jobs:
with:
persist-credentials: false
- name: Get latest CMake and ninja
uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- name: Run CMake
run: cmake -S . -B build -DCMAKE_TOOLCHAIN_FILE=$EMSDK/upstream/emscripten/cmake/Modules/Platform/Emscripten.cmake -GNinja
- name: Build
@@ -487,7 +484,7 @@ jobs:
with:
persist-credentials: false
- name: Get latest CMake and ninja
uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- name: Check that the job runs natively on arm64
run: uname -m && test "$(uname -m)" = aarch64
- name: Run CMake
+7 -5
View File
@@ -90,7 +90,7 @@ jobs:
with:
persist-credentials: false
- name: Get latest CMake and ninja
uses: lukka/get-cmake@16e8153a8b4918849d92aad131befe67a3705daa # v4.5.0
uses: lukka/get-cmake@f86dd60acae0d132056913e248bdabf0e0580b7a # v4.4.5
- 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,11 +212,13 @@ jobs:
- uses: actions/checkout@3d3c42e5aac5ba805825da76410c181273ba90b1 # v7.0.1
with:
persist-credentials: false
# 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
# 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
with:
cmakeVersion: '^4.5.0'
cmakeVersion: 4.3.4
# 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)
+1 -2
View File
@@ -165,8 +165,7 @@ std::ifstream f("example.json");
json data = json::parse(f);
```
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:
If using modules (enabled with `NLOHMANN_JSON_BUILD_MODULES`), this example becomes:
```cpp
import std;
import nlohmann.json;
+1 -3
View File
@@ -58,9 +58,7 @@ is not UTF-8 encoded and `error_handler` is set to `strict`
## Complexity
Linear in the size of the result. With an `indent`, every line starts with up to `indent` characters per nesting level,
so the result can be larger than the value by a factor of its nesting depth (see
[Parsing untrusted input](../../features/parsing/untrusted_input.md#nesting-depth)).
Linear.
## Notes
+1 -2
View File
@@ -18,8 +18,7 @@ Strong exception safety: if an exception occurs, the original value stays intact
## Complexity
Linear in the size of the result. Every key repeats the path of its value, so the keys can be larger than the value by a
factor of its nesting depth (see [Parsing untrusted input](../../features/parsing/untrusted_input.md#nesting-depth)).
Linear in the size of the JSON value.
## Notes
+2 -4
View File
@@ -69,10 +69,8 @@ Strong guarantee: if an exception is thrown, there are no changes in the JSON va
## Exceptions
- Throws [parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110) if the given input ends prematurely,
if the end of the file was not reached when `strict` was set to true, or if a string at the end of the value is not
terminated by 0xFF although a byte follows it (also when `strict` is false: the byte that ends the string is
taken from the input, so the next value would be lost)
- Throws [parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110) if the given input ends prematurely or
the end of the file was not reached when `strict` was set to true
- Throws [parse_error.112](../../home/exceptions.md#jsonexceptionparse_error112) if a parse error occurs, for instance
an invalid byte, a string that is not valid UTF-8, or an object key that is not a string
+1 -5
View File
@@ -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.
@@ -27,7 +27,7 @@ comparison of two [`json_view`](../basic_json_view/index.md) documents has a fix
and does not depend on it either.
The call stack that these operations need grows with the limit: roughly *a few kilobytes plus a cost per level times the
limit*, where the cost per level is up to about 1.8 KiB in an unoptimized and up to about 0.5 KiB in an optimized build
limit*, where the cost per level is up to about 2.3 KiB in an unoptimized and up to about 0.5 KiB in an optimized build
(see [Stack needed](#stack-needed)). The default of `128` levels is tuned for threads with ordinary stacks of a few
hundred kilobytes or more. Set a lower limit if your threads have small stacks (RTOS tasks, fibers, threads of the musl
C
@@ -67,7 +67,7 @@ When the macro is not defined, the library defines it to its default value.
the levels that are descended into are counted, so the count never exceeds the limit, not even when user code (a
copy constructor of a custom base class, say) copies a value while a copy is going on. A byte holds `255` at
most, and the limit stays below that, so that the count cannot wrap around. (More levels would hardly be
useful: `254` levels need up to 448 KiB of stack in an unoptimized build already, twice as much as the
useful: `254` levels need up to 576 KiB of stack in an unoptimized build already, twice as much as the
default.)
### Stack needed
@@ -83,7 +83,7 @@ Unoptimized (`-O0`):
| Operation | limit 16 | limit 32 | limit 64 | limit 128 | limit 254 |
|---|---:|---:|---:|---:|---:|
| `dump()` and `dump(indent)`, `operator<<` | 16 / 16 | 16 / 16 | 32 / 32 | 48 / 48 | 96 / 96 |
| `dump()` and `dump(indent)`, `operator<<` | 48 / 32 | 80 / 64 | 144 / 128 | 288 / 256 | 576 / 512 |
| copy construction and assignment | 32 / 16 | 48 / 32 | 112 / 80 | 224 / 144 | 432 / 304 |
| `==` | 16 / 16 | 16 / 16 | 16 / 16 | 48 / 32 | 96 / 48 |
| `<=>` (C++20) | 16 / 16 | 16 / 16 | 32 / 32 | 64 / 64 | 144 / 128 |
@@ -123,24 +123,23 @@ The rule of thumb is
> stack needed ≈ a few KiB + cost per level × limit
with a cost per level of up to 1.8 KiB (conversion to another `basic_json` type at `-O0` with Clang; 1.3 KiB with
GCC), 1.7 KiB for copying and merging (1.3 KiB with GCC), 0.4 KiB for `dump`, and 0.1 to 0.5 KiB for most other
operations at `-O0`; and 0.5 KiB or less at `-O2`. The numbers come from the difference between the limits `128` and
`254` in the tables, so they are rough: other compilers, other targets (the frames of x86-64 code are about as large),
other standard libraries, `JSON_DIAGNOSTICS`, and sanitizers change them. Measure with your own tool chain (see the
example below) rather than relying on the tables. The stack that your own code and the operating system need comes on
top of these numbers.
with a cost per level of up to 2.3 KiB (`dump` at `-O0` with Clang; 2.1 KiB with GCC), 1.7 KiB for copying and merging
(1.3 KiB with GCC), and 0.1 to 0.5 KiB for most other operations at `-O0`; and 0.5 KiB or less at `-O2`. The numbers
come from the difference between the limits `128` and `254` in the tables, so they are rough: other compilers,
other targets (the frames of x86-64 code are about as large), other standard libraries, `JSON_DIAGNOSTICS`, and
sanitizers change them. Measure with your own tool chain (see the example below) rather than relying on the tables.
The stack that your own code and the operating system need comes on top of these numbers.
Which limit to choose, for the stack that you can spare for the library (the largest limit of those measured
for which the slowest operation needs at most that much):
| Stack for the library | optimized (`-O2`) | unoptimized (`-O0`) |
|---|---:|---:|
| 32 KiB | 64 | 16 |
| 64 KiB | 128 | 32 |
| 128 KiB (the default stack of threads on musl) | 254 | 64 |
| 256 KiB | 254 | 128 |
| 512 KiB | 254 | 254 |
| 32 KiB | 64 | 0 |
| 64 KiB | 128 | 16 |
| 128 KiB (the default stack of threads on musl) | 254 | 32 |
| 256 KiB | 254 | 64 |
| 512 KiB | 254 | 128 |
| 1 MiB or more | 254 | 254 |
### Speed
+10 -12
View File
@@ -89,21 +89,19 @@ This differs from `#!cpp std::map`, where the same operations are O(log n).
!!! warning "Quadratic cost of building large objects"
Because every insertion scans all elements inserted so far, building an object of `n` distinct keys costs
**O(n²)** in total. This applies to filling an [`ordered_json`](ordered_json.md) object key by key (with
`operator[]`, `emplace`, or `insert`) and, for now, to reading one with a binary reader such as
[`from_cbor`](basic_json/from_cbor.md) ([#6104](https://github.com/nlohmann/json/issues/6104)). Parsing JSON text
is not affected: the parser finds the keys of an object with many members in a hash table and takes linear time.
**O(n²)** in total. This applies to filling an [`ordered_json`](ordered_json.md) object key by key as well as to
parsing one, since the parser inserts each key as it is read.
The cost is negligible for the object sizes typically found in configuration files or API payloads, but it grows
steeply for machine-generated objects with many thousands of keys. Measured with Apple clang 21, `-O2 -DNDEBUG`,
arm64, for a flat object of `n` keys (best of seven runs):
steeply for machine-generated objects with many thousands of keys. Measured with `-O2 -DNDEBUG` for parsing a flat
object of `n` keys, relative to `#!cpp nlohmann::json` (which uses `#!cpp std::map`):
| `n` | `json::parse` | `ordered_json::parse` | `ordered_json`, key by key | `ordered_json::from_cbor` |
|--------|---------------|-----------------------|----------------------------|---------------------------|
| 2000 | 0.3 ms | 0.1 ms | 4.5 ms | 4.4 ms |
| 4000 | 0.5 ms | 0.2 ms | 17.1 ms | 16.8 ms |
| 8000 | 0.9 ms | 0.3 ms | 67.0 ms | 66.8 ms |
| 16 000 | 2.0 ms | 0.7 ms | 282.4 ms | 282.4 ms |
| `n` | `json` | `ordered_json` | factor |
|--------|--------|----------------|--------|
| 2000 | 0.7 ms | 3.6 ms | 5× |
| 4000 | 0.8 ms | 14.0 ms | 19× |
| 8000 | 1.6 ms | 67.8 ms | 43× |
| 16 000 | 3.3 ms | 181.6 ms | 54× |
If key order matters for objects of that size, consider a container with a lookup index, such as
[`nlohmann::fifo_map`](https://github.com/nlohmann/fifo_map)
@@ -181,10 +181,7 @@ of the message are reported as [parse_error.110](../../home/exceptions.md#jsonex
arrays and objects with up to four elements that are terminated by 0xFE, unsorted object keys, or a 0xFF after a
string that would also end without it, are accepted. A second 0xFF is not a terminator but an empty string.
Strings must be valid UTF-8, and a string at the very end of a message must be terminated by 0xFF. This also
holds when `strict` is false and more data follows the value: the byte that would end the string belongs to the
next value, and reading it would remove it from the input, so the missing 0xFF is reported as
[parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110).
Strings must be valid UTF-8, and a string at the very end of a message must be terminated by 0xFF.
Duplicate object keys are accepted; the last value wins (`ordered_json` keeps the position of the first occurrence).
The specification does not say how to treat them; the HikoGUI reference decoder keeps the first value.
+2 -14
View File
@@ -9,19 +9,7 @@ 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), 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.
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.
## Example
When using modules rather than headers, the previous example for creating a `json` object through a JSON file, would instead be:
@@ -79,7 +67,7 @@ and should not be used directly:
## Known issues
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).
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).
!!! info "Known compiler issues"
@@ -64,13 +64,13 @@ stack for the nesting.)
The call stack still needs room for the levels that are recursed into, and the default limit assumes a stack of ordinary
size. The stack that an operation needs is roughly proportional to the limit; with the default of 128 levels, the most
demanding operations (copying a value and converting it to another `basic_json` type, in an unoptimized build) needed
up to 224 KiB, and an optimized build needed 48 KiB or less, in measurements on macOS with arm64. The most demanding
operation needed this much stack at the limits `0`, `32`, `128`, and `254`:
demanding operation (`dump` in an unoptimized build) needed up to 288 KiB, and an optimized build needed 48 KiB or less,
in measurements on macOS with arm64. The most demanding operation needed this much stack at the limits `0`, `32`,
`128`, and `254`:
| Stack needed, in KiB | limit 0 | limit 32 | limit 128 (default) | limit 254 |
|---|---:|---:|---:|---:|
| unoptimized build (`-O0`) | 16 or less | 64 | 224 | 448 |
| unoptimized build (`-O0`) | 16 or less | 80 | 288 | 576 |
| optimized build (`-O2`) | 16 or less | 16 or less | 48 | 112 |
A thread with a smaller stack (a task of a real-time operating system, a fiber, or a thread of the musl C library, whose
@@ -81,20 +81,6 @@ result. See the [documentation of the macro](../../api/macros/json_recursion_dep
the speed, and the rules for choosing a value. Destroying a value (its destructor) recurses over the same number of
levels and then continues without the call stack, and needs 32 KiB or less at every limit.
!!! warning "Indented output and flattened keys grow with the depth"
Some results are larger than the value by a factor of its nesting depth.
[`dump`](../../api/basic_json/dump.md) with an `indent` of `n` (and likewise `operator<<` with `std::setw(n)` and
[`basic_json_view::dump`](../../api/basic_json_view/dump.md)) writes up to `n` characters per nesting level in
front of every line, and [`flatten`](../../api/basic_json/flatten.md) repeats the path of every value in its key.
For the 80,001-byte array `[1,[1,...[1,1]...]]` with 20,000 levels, `dump(1)` returns 600 MB, `dump(4)` 2.4 GB,
and the keys of `flatten()` hold 400 MB. A compact `dump()` without indentation stays the size of the value. If you
pretty-print, log, or flatten untrusted input, limit its nesting depth while parsing, for example with a
[parser callback](parser_callbacks.md#recipe-max-nesting-depth-via-a-callback): with a limit of `d`, every line has
at most `n * d` indentation characters, and every flattened key has at most `d` reference tokens.
[`JSON_RECURSION_DEPTH_LIMIT`](../../api/macros/json_recursion_depth_limit.md) does not help here: it changes only
how much of the call stack a walk uses, never its result, and it does not limit the depth that `parse()` accepts.
## Input size
The library does not limit the overall size of a JSON text; a value nested or wide enough will use memory
@@ -182,20 +168,6 @@ values for a repeated key ends up in the parsed object. If your application must
silently resolving them one way or another, see the
[parser callback recipe for rejecting duplicate keys](parser_callbacks.md#recipe-rejecting-duplicate-object-keys).
## Objects with many keys in `ordered_json`
[`ordered_json`](../../api/ordered_json.md) keeps the members of an object in a vector in insertion order
([`ordered_map`](../../api/ordered_map.md)) and finds a key by searching all members. Parsing JSON text into an
`ordered_json` avoids that search for objects with many keys and takes linear time. The binary readers
([`from_cbor`](../../api/basic_json/from_cbor.md), [`from_msgpack`](../../api/basic_json/from_msgpack.md),
[`from_ubjson`](../../api/basic_json/from_ubjson.md), [`from_bjdata`](../../api/basic_json/from_bjdata.md),
[`from_bson`](../../api/basic_json/from_bson.md), and [`from_bon8`](../../api/basic_json/from_bon8.md)) do not yet:
reading an object of `n` keys into an `ordered_json` costs time proportional to `n²`. A flat object of 40,000 keys
(about 300 KB of CBOR) takes about 1.3 s, against a few milliseconds as JSON text or into a `json`
([#6104](https://github.com/nlohmann/json/issues/6104)). `json` is not affected. If you read untrusted binary input
into `ordered_json`, bound the input size more tightly, read it into a `json`, or reject objects with many keys in a
[SAX handler](sax_interface.md).
## Numbers
A number whose value cannot be represented — for instance `1E1000`, which overflows `double` — is rejected while
@@ -227,11 +199,9 @@ indices (or the pointer as a whole) before using them, or use [`at`](../../api/b
- Wrap parsing in a `#!cpp try`/`#!cpp catch` block, or use `allow_exceptions=false`/`accept()` if your environment
cannot use exceptions; never let `JSON_NOEXCEPTION`'s `abort()` be the first time you think about error handling.
- If the input's nesting depth matters to you (for example because you pretty-print, log, or flatten it), enforce your
own limit with a [parser callback](parser_callbacks.md#recipe-max-nesting-depth-via-a-callback) or a
- If the input's nesting depth matters to you, enforce your own limit with a
[parser callback](parser_callbacks.md#recipe-max-nesting-depth-via-a-callback) or a
[SAX handler](sax_interface.md); the library bounds the call stack but not memory use.
- If you read untrusted binary input into `ordered_json`, mind that objects with many keys are
[slow to read](#objects-with-many-keys-in-ordered_json).
- Bound the size of the input itself before parsing, independent of the library's own bounded allocations for binary
format lengths.
- Decide up front how you want a string with invalid UTF-8 — from any source, not only parsing — to be serialized
-2
View File
@@ -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:
-3
View File
@@ -269,9 +269,6 @@ 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
@@ -48,11 +48,10 @@ namespace detail
{
/*!
@brief implements binary to decimal floating-point conversion: the shortest
digits of Zmij (see zmij.hpp) for IEEE 754 binary64 numbers, and the Grisu2
algorithm for all other formats.
@brief implements the Grisu2 algorithm for binary to decimal floating-point
conversion.
The Grisu2 implementation is a slightly modified version of the reference
This implementation is a slightly modified version of the reference
implementation which may be obtained from
http://florian.loitsch.com/publications (bench.tar.gz).
@@ -88,9 +88,8 @@ JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 2
The limit @ref max_valueless_container_size applies to each container on its
own, so on its own it lets 9 bytes announce 1048576 values, and every further
8 bytes (a row of an optimized array of arrays) another 1048576. The elements
of all containers of a valueless type in one input are therefore added up, and
the sum must stay below this base
8 bytes (a row of an optimized array of arrays) another 1048576. The elements of all containers of a valueless type
in one input are therefore added up, and the sum must stay below this base
plus @ref valueless_elements_per_byte for every byte read so far. The base is
the per-container limit, so a container that was accepted on its own before
the sum was introduced is still accepted at the start of an input.
@@ -300,17 +299,6 @@ class binary_reader
JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert) LCOV_EXCL_LINE
}
// BON8: a string ends at the first byte that cannot continue it. If
// that byte follows the value, the reader has already taken it from
// the input and holds it in bon8_pushback. Without the end-of-input
// check below it would be dropped, and the next read would start
// behind it, so report the missing 0xFF instead.
if (result && !strict && input_format == input_format_t::bon8 && bon8_pushback_size != 0)
{
get_bon8();
return last_byte_error(exception_id::unexpected_end_of_input, "string at the end of the value is not terminated by 0xFF", "value", "");
}
// strict mode: next byte must be EOF
if (result && strict)
{
+36 -113
View File
@@ -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
cannot read again: unlike std::vector::push_back(), appending a character
takes no reference to a local, and is a few instructions when there 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.
copied out of its window: unlike std::vector<char>::push_back(), appending a
character takes no reference to a local, and is a few instructions when there
is room.
*/
template<typename CharType>
class token_text_buffer
class token_carry_buffer
{
public:
static constexpr std::size_t head() noexcept
{
return 4096;
}
/// 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
token_carry_buffer() = default;
token_carry_buffer(const token_carry_buffer&) = delete;
token_carry_buffer& operator=(const token_carry_buffer&) = delete;
token_carry_buffer(token_carry_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
{
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;
token_carry_buffer& operator=(token_carry_buffer&&) = delete;
~token_carry_buffer() = default;
void clear() noexcept
{
m_end = m_data.get();
}
bool empty() const noexcept
{
return m_end == m_data.get();
}
void push_back(CharType c)
void push_back(char c)
{
if (JSON_HEDLEY_UNLIKELY(m_end == m_capacity_end))
{
make_room(1);
grow(1);
}
*m_end++ = c;
}
/// drop the last character
void pop_back() noexcept
{
JSON_ASSERT(!empty());
--m_end;
}
void append(const CharType* first, const CharType* last)
void append(const char* first, const char* 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);
return;
grow(n);
}
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()
/// characters, so that dropping the middle keeps the last tail() of them
JSON_HEDLEY_NEVER_INLINE void append_long(const CharType* first, std::size_t n)
/// make room for @a extra more characters
JSON_HEDLEY_NEVER_INLINE void grow(std::size_t extra)
{
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();
make_room(piece);
std::memcpy(m_end, first, piece * sizeof(CharType));
m_end += piece;
first += piece;
n -= piece;
std::memcpy(data.get(), m_data.get(), size);
}
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
/// middle of a long token instead of growing beyond limit()
JSON_HEDLEY_NEVER_INLINE void make_room(std::size_t extra)
{
// 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;
std::unique_ptr<char[]> m_data{}; // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays,readability-redundant-member-init)
char* m_end = nullptr;
char* 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
+15 -30
View File
@@ -215,19 +215,6 @@ template<typename ArrayType>
inline void reserve_array(ArrayType& /*arr*/, std::size_t /*len*/, priority_tag<0> /*unused*/)
{}
/// reserve capacity for @a count elements in array @a arr, where @a count is
/// at most reserve_cap() already (see json_sax_dom_error_state::reserve_count)
template<typename ArrayType>
auto reserve_array_capped(ArrayType& arr, std::size_t count, priority_tag<1> /*unused*/)
-> decltype(arr.reserve(count), void())
{
arr.reserve(count);
}
template<typename ArrayType>
inline void reserve_array_capped(ArrayType& /*arr*/, std::size_t /*count*/, priority_tag<0> /*unused*/)
{}
/*!
@brief reports an object or array whose announced size exceeds max_size()
@@ -470,35 +457,32 @@ class json_sax_dom_error_state
announces more than what is left of that is given what is left, and
grows as its elements arrive. Without the position of the input (the
parser is not driven by a binary_reader that is running) nothing is
bounded but reserve_cap() for each array.
bounded but the cap of reserve_array().
The common case, an array whose reservation is no more than the credit
left, costs a comparison and a subtraction. An array is charged what is
reserved for it, at most reserve_cap() elements, not what it announces, so
an array of more elements does not take credit from the arrays nested in
it.
The common case, an array that announces no more than the credit left,
costs a comparison and a subtraction. It is charged what it announces, which
for an array of more than reserve_cap() elements is more than reserve_array()
reserves for it, which its own elements refill as they are read.
*/
std::size_t reserve_count(const std::size_t len) noexcept
{
const std::size_t count = (std::min)(len, reserve_cap());
if (JSON_HEDLEY_LIKELY(count <= reserve_credit))
if (JSON_HEDLEY_LIKELY(len <= reserve_credit))
{
reserve_credit -= count;
return count;
reserve_credit -= len;
return len;
}
return reserve_count_slowly(count);
return reserve_count_slowly(len);
}
private:
/// @a count is at most reserve_cap()
JSON_HEDLEY_NEVER_INLINE
std::size_t reserve_count_slowly(std::size_t count) noexcept
std::size_t reserve_count_slowly(const std::size_t len) noexcept
{
constexpr std::size_t max_size = (std::numeric_limits<std::size_t>::max)();
if (input_position == nullptr)
{
reserve_credit = max_size;
return count;
return len;
}
// refill the credit with 'reserved_elements_per_byte' for every
@@ -516,6 +500,7 @@ class json_sax_dom_error_state
credit_position = position;
}
std::size_t count = (std::min)(len, reserve_cap());
count = (std::min)(count, reserve_credit);
reserve_credit -= count;
return count;
@@ -1361,7 +1346,7 @@ class json_sax_dom_parser : public json_sax_dom_error_state
if (len != detail::unknown_size())
{
reserve_array_capped(*ref->m_data.m_value.array, reserve_count(len), priority_tag<1> {});
reserve_array(*ref->m_data.m_value.array, reserve_count(len), priority_tag<1> {});
}
}
@@ -1709,7 +1694,7 @@ class json_sax_dom_binary_parser : public json_sax_dom_error_state
if (len != detail::unknown_size())
{
reserve_array_capped(*ref_stack.back()->m_data.m_value.array, reserve_count(len), priority_tag<1> {});
reserve_array(*ref_stack.back()->m_data.m_value.array, reserve_count(len), priority_tag<1> {});
}
return true;
@@ -2001,7 +1986,7 @@ class json_sax_dom_callback_parser : public json_sax_dom_error_state
if (len != detail::unknown_size())
{
reserve_array_capped(*ref_stack.back()->m_data.m_value.array, reserve_count(len), priority_tag<1> {});
reserve_array(*ref_stack.back()->m_data.m_value.array, reserve_count(len), priority_tag<1> {});
}
}
+9 -47
View File
@@ -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.push_back(static_cast<char_type>(data[i]));
}
token_string.insert(token_string.end(), data, data + n);
}
/// 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
// 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);
}
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 out;
return token_string;
}
/// 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;
// 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();
// escape control characters
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)
@@ -257,7 +257,7 @@ struct ieee_binary_format<53> // binary64
These formats (float, double, and long double where it is binary64, e.g.
with MSVC or on Apple arm64) are converted by parse_float_native(). The
predicate is the one the serializer uses to choose to_chars() over snprintf.
predicate is the one the serializer uses to choose Grisu2.
*/
template<typename FloatType>
struct has_native_float_format
+135 -365
View File
@@ -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;
}
-10
View File
@@ -230,16 +230,6 @@
// detail/recursion_depth_limit.hpp. Like JSON_NO_THREAD_LOCAL it is neither part
// of the ABI tag nor undefined at the end of json.hpp.
// forced inlining of the serializer's helpers only in optimized builds: at -O0,
// GCC and Clang give every inlined copy its own stack slots, which made the
// recursive frame of serializer::dump_container() about 2.3 KB (MSVC does not
// expand __forceinline at /Ob0, so it keeps it)
#if defined(__OPTIMIZE__) || defined(_MSC_VER)
#define JSON_INTERNAL_SERIALIZER_INLINE JSON_HEDLEY_ALWAYS_INLINE
#else
#define JSON_INTERNAL_SERIALIZER_INLINE inline
#endif
// allow disabling exceptions
#if (defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)) && !defined(JSON_NOEXCEPTION)
#define JSON_THROW(exception) throw exception
@@ -11,7 +11,6 @@
// clean up
#undef JSON_ASSERT
#undef JSON_INTERNAL_CATCH
#undef JSON_INTERNAL_SERIALIZER_INLINE
#undef JSON_THROW
#undef JSON_PRIVATE_UNLESS_TESTED
#undef NLOHMANN_BASIC_JSON_TPL_DECLARATION
@@ -915,7 +915,7 @@ class binary_writer
JSON_THROW(out_of_range::create(exception_id::subtype_out_of_range, concat("subtype ", std::to_string(subtype), " is too large for ", what, " (max 255)"), &j));
}
/// @throw other_error.502 always
/// @throw other_error.407 always
JSON_HEDLEY_NO_RETURN JSON_HEDLEY_NEVER_INLINE
static void throw_size_marker_required(const BasicJsonType& j)
{
+9 -10
View File
@@ -265,7 +265,7 @@ class serializer
for a container; writing them from here spares each the entry and exit of
that function.
*/
JSON_INTERNAL_SERIALIZER_INLINE void dump_element(const BasicJsonType& val,
JSON_HEDLEY_ALWAYS_INLINE void dump_element(const BasicJsonType& val,
const std::size_t current_indent,
const std::size_t depth)
{
@@ -971,7 +971,7 @@ class serializer
}
/// write out the bytes pending in @ref string_buffer and reset @a bytes
JSON_INTERNAL_SERIALIZER_INLINE void emit_pending(std::size_t& bytes)
JSON_HEDLEY_ALWAYS_INLINE void emit_pending(std::size_t& bytes)
{
if (bytes != 0)
{
@@ -983,7 +983,7 @@ class serializer
/// write buffer and reset index if fewer than 13 bytes are left, as this
/// is the maximal number of bytes to be written ("\uxxxx\uxxxx\0") for one
/// code point
JSON_INTERNAL_SERIALIZER_INLINE void reserve_string_buffer(std::size_t& bytes)
JSON_HEDLEY_ALWAYS_INLINE void reserve_string_buffer(std::size_t& bytes)
{
if (string_buffer.size() - bytes < 13)
{
@@ -1344,7 +1344,7 @@ class serializer
inlining both into the pretty-printing loops once @ref dump_escaped
has grown, which made indented output up to 13% slower
*/
JSON_INTERNAL_SERIALIZER_INLINE void put_indent(std::size_t indent)
JSON_HEDLEY_ALWAYS_INLINE void put_indent(std::size_t indent)
{
// closing braces at the outermost level ask for no indentation at all
if (indent == 0)
@@ -1398,7 +1398,7 @@ class serializer
its room and four stores of the indentation, see @ref put_short_literal_indent.
*/
template<std::size_t N>
JSON_INTERNAL_SERIALIZER_INLINE void put_literal_indent(const char (&s)[N], const std::size_t indent) // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
JSON_HEDLEY_ALWAYS_INLINE void put_literal_indent(const char (&s)[N], const std::size_t indent) // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
{
if (JSON_HEDLEY_LIKELY(put_short_literal_indent(s, indent)))
{
@@ -1418,7 +1418,7 @@ class serializer
@a indent is wider or the write buffer lacks the room.
*/
template<std::size_t N>
JSON_INTERNAL_SERIALIZER_INLINE bool put_short_literal_indent(const char (&s)[N], const std::size_t indent) // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
JSON_HEDLEY_ALWAYS_INLINE bool put_short_literal_indent(const char (&s)[N], const std::size_t indent) // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
{
constexpr std::size_t length = N - 1;
if (indent > 32 || write_buffer_pos + length + 32 > write_buffer.size())
@@ -1445,7 +1445,7 @@ class serializer
write-through path for oversized runs.
*/
template<std::size_t N>
JSON_INTERNAL_SERIALIZER_INLINE void put_literal(const char (&s)[N]) // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
JSON_HEDLEY_ALWAYS_INLINE void put_literal(const char (&s)[N]) // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
{
static_assert(N >= 2, "put_literal expects a non-empty string literal");
// the array bound counts the terminating NUL, which is not written
@@ -2033,9 +2033,8 @@ class serializer
}
// If number_float_t is an IEEE-754 single or double precision number,
// use to_chars() to produce short numbers which are guaranteed to
// round-trip, using strtof and strtod, resp. (the shortest digits of
// Zmij for binary64, the Grisu2 algorithm for binary32).
// use the Grisu2 algorithm to produce short numbers which are
// guaranteed to round-trip, using strtof and strtod, resp.
//
// NB: The test below works if <long double> == <double>.
static constexpr bool is_ieee_single_or_double
+1 -1
View File
@@ -849,7 +849,7 @@ class basic_json_view
return !navigation::editable() || m_doc->edits == nullptr;
}
/// the member of this object with @a key (the first one if the key occurs more than once), or nullptr
/// the member of this object with @a key (the last one if the key occurs more than once), or nullptr
NLOHMANN_VIEW_ALWAYS_INLINE const node* find_key(string_view_t key) const
{
return find_key(key, std::integral_constant<bool, is_editable> {});
+211 -596
View File
File diff suppressed because it is too large. Load diff
+1 -1
View File
@@ -11016,7 +11016,7 @@ class basic_json_view
return !navigation::editable() || m_doc->edits == nullptr;
}
/// the member of this object with @a key (the first one if the key occurs more than once), or nullptr
/// the member of this object with @a key (the last one if the key occurs more than once), or nullptr
NLOHMANN_VIEW_ALWAYS_INLINE const node* find_key(string_view_t key) const
{
return find_key(key, std::integral_constant<bool, is_editable> {});
-7
View File
@@ -1,12 +1,5 @@
cmake_minimum_required(VERSION 3.13...4.0)
# The unit tests use no C++ modules. Without this, CMake 4.5 scans the C++20 and
# newer test targets and builds a `std` module for them, compiling the standard
# library's module sources with the test warning flags (which fails with
# -Werror) or failing to configure when the libc++ module sources are missing.
# The module test in tests/module_cpp20 is a separate project and unaffected.
set(CMAKE_CXX_SCAN_FOR_MODULES OFF)
option(JSON_Valgrind "Execute test suite with Valgrind." OFF)
option(JSON_FastTests "Skip expensive/slow tests." OFF)
option(JSON_TestSimdutf "Build the unit tests against the simdutf UTF-8 validation backend." OFF)
+9 -3
View File
@@ -1,6 +1,11 @@
# `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)
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")
project(json_test CXX)
@@ -8,6 +13,7 @@ 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")
+2 -2
View File
@@ -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 4.5 or newer;
// see CMakeLists.txt.
// across GCC, Clang, and MSVC. This requires C++23 and CMake's (experimental)
// import-std support; see CMakeLists.txt.
int main()
{
// basic_json / json: parsing and value access
+3 -15
View File
@@ -608,26 +608,14 @@ TEST_CASE("BON8")
CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec), "[json.exception.parse_error.110] parse error at byte 2: syntax error while parsing BON8 value: expected end of input; last byte: 0x90", json::parse_error&);
CHECK(json::from_bon8(vec, true, false).is_discarded());
// the byte after a string that ends a container: without strict, the
// missing 0xFF is reported, as the byte has been taken from the input
// the byte after a string that ends a container
const bytes vec2 = {0x81, 'a', 0x90};
CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec2, false), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0x90", json::parse_error&);
CHECK(json::from_bon8(vec2, false, false).is_discarded());
CHECK(json::from_bon8(vec2, false) == json({"a"}));
CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec2), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: expected end of input; last byte: 0x90", json::parse_error&);
const bytes vec3 = {0x81, 'a', 0xC2, 0x00};
CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec3, false), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0xC2", json::parse_error&);
CHECK(json::from_bon8(vec3, false) == json({"a"}));
CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec3), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: expected end of input; last byte: 0xC2", json::parse_error&);
// with a terminated string, strict = false leaves the next value in the stream
std::istringstream terminated(std::string("\x61\xFF\x90", 3));
CHECK(json::from_bon8(terminated, false) == "a");
CHECK((terminated.tellg() == 2));
CHECK(json::from_bon8(terminated, false) == 0);
// without the terminator, the next value would be lost
std::istringstream unterminated(std::string("\x61\x90", 2));
CHECK_THROWS_WITH_AS(_ = json::from_bon8(unterminated, false), "[json.exception.parse_error.110] parse error at byte 2: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0x90", json::parse_error&);
}
}
-27
View File
@@ -2898,33 +2898,6 @@ TEST_CASE("CBOR - open arrays reserve only what the input has backed")
CHECK(j.back() == 2);
}
SECTION("an array that announces more than 16384 elements is charged what it is reserved")
{
// an array of 20000 elements (header 9A 00 00 4E 20) and three nested
// arrays of 16384: the four reservations of 16384 add up to the credit
// of 65,536. Charged the 20000 it announces, the outer array would
// leave the innermost one less than it announces
std::vector<std::uint8_t> input = {0x9A, 0x00, 0x00, 0x4E, 0x20};
const auto nested = utils::repeated({0x99, 0x40, 0x00}, 3);
input.insert(input.end(), nested.begin(), nested.end());
json result;
dom_parser parser(result, false);
CHECK_FALSE(json::sax_parse(input, &parser, json::input_format_t::cbor));
const json* node = &result;
for (int level = 0; level < 4; ++level)
{
CAPTURE(level)
REQUIRE(node->is_array());
CHECK(node->get_ref<const json::array_t&>().capacity() == 16384);
if (level < 3)
{
REQUIRE(node->size() == 1);
node = &node->front();
}
}
}
SECTION("a DOM parser that a parse has finished with is not bounded by the input of that parse")
{
// the DOM parser learns where the reader counts its characters, and
-123
View File
@@ -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,125 +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);
// false positive: append() on an empty buffer allocates in append_long() before writing
// @infer-ignore NULLPTR_DEREFERENCE
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'});
}
}
-113
View File
@@ -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
-321
View File
@@ -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());
}
}