mirror of
https://github.com/nlohmann/json.git
synced 2026-11-11 18:08:22 +00:00
Compare commits
1
Commits
| Author | SHA1 | Date | |
|---|---|---|---|
 Niels Lohmann
|
06b11f80fd |
No files matched your search
@@ -89,10 +89,8 @@ Strong guarantee: if an exception is thrown, there are no changes in the JSON va
|
||||
- Throws [out_of_range.406](../../home/exceptions.md#jsonexceptionout_of_range406) if a high-precision number, or a
|
||||
float64 when `number_float_t` is `float`, does not fit into `number_float_t`
|
||||
- Throws [out_of_range.408](../../home/exceptions.md#jsonexceptionout_of_range408) if the count of an optimized
|
||||
container exceeds the capacity of the container (or of `std::size_t`; an array of type `N` is empty, so only the
|
||||
latter applies to it), if an optimized array of `Z`, `T`, or `F` has more than 1,048,576 elements, or if the
|
||||
optimized arrays of `Z`, `T`, and `F` in the input together have more than 1,048,576 elements plus 4 for every byte
|
||||
read so far
|
||||
container exceeds the capacity of the container (or of `std::size_t`), or if an optimized array of `Z`, `T`, or `F` has
|
||||
more than 1,048,576 elements
|
||||
|
||||
## Complexity
|
||||
|
||||
@@ -134,9 +132,6 @@ Linear in the size of the input.
|
||||
- Extended container support (1) to include types with lvalue-only ADL `begin`/`end` (matching `std::begin`/`std::end` semantics) in version 3.13.0.
|
||||
- Extended overload (2) to accept heterogeneous iterator+sentinel pairs (C++20 ranges support) in version 3.13.0.
|
||||
- Added `error_handler` parameter in version 3.13.0.
|
||||
- Report `start_array(0)` to a SAX handler for an optimized array of type `N` (`[$N#n`), whatever its count, in version
|
||||
3.13.0.
|
||||
- Limited the total number of elements of optimized arrays of `Z`, `T`, and `F` in one input in version 3.13.0.
|
||||
|
||||
!!! warning "Deprecation"
|
||||
|
||||
|
||||
@@ -117,8 +117,5 @@ Linear in the size of the JSON value `j`.
|
||||
- Added `error_handler` parameter in version 3.13.0. Its default, `keep`, writes the bytes of a string or object key
|
||||
that is not valid UTF-8 unchanged, as before; `strict` (the default if
|
||||
[`JSON_STRICT_BINARY_UTF8`](../macros/json_strict_binary_utf8.md) is enabled) throws `type_error.316`.
|
||||
- Writes arrays of `Z`, `T`, or `F` without the `$` type annotation (`[#n Z Z ...`) once their elements in one call
|
||||
add up to more than 1,048,576, in version 3.13.0, so that `from_ubjson` can read the output back. Such output is
|
||||
larger: 270,000 rows of 100 `null` values take 26.8 MB instead of 1.35 MB.
|
||||
- Throws `type_error.321` for a discarded value since version 3.13.0; previously, a discarded value nested in an
|
||||
array or object was silently skipped, producing invalid UBJSON.
|
||||
@@ -122,18 +122,9 @@ The library uses the following mapping from JSON values types to UBJSON types ac
|
||||
already is the value. Its declared count is therefore the only thing that decides how much memory the receiving side
|
||||
allocates, and a handful of bytes can describe billions of elements. `from_ubjson` rejects such an array with
|
||||
[`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408) when the count exceeds 1,048,576
|
||||
(`1 << 20`), or when the counts of all such arrays in the input add up to more than 1,048,576 plus 4 for every byte
|
||||
read so far. `to_ubjson` therefore writes an array of these types in the counted but untyped form when it is longer
|
||||
than that, or when it would bring the total of the typed arrays written so far above 1,048,576: the `$` type marker
|
||||
is dropped, the `#` count is kept, and every element is written with its own marker (`[#l 1048577 Z Z ...`), so
|
||||
everything it produces can be read back. Only input from another encoder, or written by version 3.12.0 and earlier of
|
||||
this library, can exceed the limit: for example, 1,100 rows of 1,000 `null` values or 210,000 rows of 25, each with
|
||||
a `$Z` annotation. Version 3.12.0 writes such a row in 5 bytes (6 above 255 elements), so rows of 20 or fewer such
|
||||
values are never rejected. Objects and untyped counted arrays are not subject to this limit.
|
||||
|
||||
An optimized array of type `N` (no-op) is empty whatever its count is, because a no-op is not a value. Its count is
|
||||
not passed on: `sax_parse` reports `start_array(0)` (versions before 3.13.0 reported the declared count), and the DOM
|
||||
parser reserves nothing for it.
|
||||
(`1 << 20`), and `to_ubjson` writes longer arrays of these types in the counted but untyped form: the `$` type marker is
|
||||
dropped, the `#` count is kept, and every element is written with its own marker (`[#l 1048577 Z Z ...`), so any value
|
||||
it produces can be read back. Objects and untyped counted arrays are not subject to this limit.
|
||||
|
||||
!!! info "Binary values"
|
||||
|
||||
@@ -189,11 +180,10 @@ The library maps UBJSON types to JSON value types as follows:
|
||||
|
||||
Every well-formed UBJSON value can be converted to a JSON value, with these exceptions: a high-precision number
|
||||
outside the range of `number_float_t` ([`out_of_range.406`](../../home/exceptions.md#jsonexceptionout_of_range406)),
|
||||
optimized arrays of `Z`, `T`, or `F` with more elements than the limit allows (1,048,576 plus 4 per byte read),
|
||||
and a count that exceeds the capacity of the container
|
||||
([`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408)). High-precision numbers that do not
|
||||
fit an integer type are stored as floating-point numbers and may lose precision. Ill-formed input is rejected with a
|
||||
parse error.
|
||||
an optimized array of `Z`, `T`, or `F` with more than 1,048,576 elements, and a count that exceeds the capacity of the
|
||||
container ([`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408)). High-precision numbers that
|
||||
do not fit an integer type are stored as floating-point numbers and may lose precision. Ill-formed input is rejected
|
||||
with a parse error.
|
||||
|
||||
!!! info "Duplicate object keys"
|
||||
|
||||
|
||||
@@ -72,22 +72,10 @@ For the binary formats, an announced size is never trusted outright:
|
||||
(reported as a parse error) instead of triggering an oversized allocation.
|
||||
- When an array announces its number of elements and the array container supports `reserve()` (as `#!cpp std::vector`,
|
||||
the default, does), the library reserves storage for at most 16384 of them upfront, regardless of how large the
|
||||
announced count is; further elements still grow the container normally as they are read. A count that no
|
||||
input backs, as in a truncated input, reserves at most that much until the parse error is reported. A parse that
|
||||
completes keeps storage for such a count only where the elements take no input at all, which the two
|
||||
[UBJSON](../binary_formats/ubjson.md) cases below cover.
|
||||
announced count is; further elements still grow the container normally as they are read.
|
||||
- An announced array or object size that exceeds what the target container could ever hold (its `max_size()`) is
|
||||
rejected immediately as [`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408), without
|
||||
attempting to allocate anything.
|
||||
- A [UBJSON](../binary_formats/ubjson.md) array of the no-op type (`[$N#<n>`) is empty whatever count it declares: a
|
||||
SAX handler is told `start_array(0)` and the DOM parser reserves nothing.
|
||||
- A UBJSON array of type `Z`, `T` or `F` has no payload, so its announced count is not bounded by the input. One array
|
||||
may announce at most 1,048,576 elements, and all such arrays of one input together may contain at most 1,048,576
|
||||
elements plus 4 for every byte read so far (checked when each array's header has been read); beyond that the input is
|
||||
rejected as [`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408). For a DOM that bounds the memory these
|
||||
arrays can need to about 80 bytes per byte of input plus about 33 MB for the first 1,048,576 elements; a SAX handler
|
||||
receives at most that many events. Every other optimized array element, and every UBJSON object member (it has a
|
||||
key), takes at least one byte of input.
|
||||
|
||||
## Strings
|
||||
|
||||
|
||||
@@ -1050,17 +1050,11 @@ The size of an array or object in a [binary format](../features/binary_formats/i
|
||||
the size following `#` for [UBJSON](../features/binary_formats/ubjson.md)/[BJData](../features/binary_formats/bjdata.md),
|
||||
or the encoded length for [CBOR](../features/binary_formats/cbor.md).
|
||||
|
||||
The exception is also thrown for [UBJSON](../features/binary_formats/ubjson.md) arrays of a type that is encoded by
|
||||
its marker alone (`Z`, `T` or `F`). Such an array has no payload, so its count alone decides how much memory is
|
||||
allocated, and a handful of bytes would otherwise describe billions of values. It is thrown if the declared count of one
|
||||
array exceeds 1,048,576 (`1 << 20`), and if the counts of all such arrays read so far in one input add up to more than
|
||||
1,048,576 plus 4 for every byte of the input read when the header of the last array has been read.
|
||||
[`to_ubjson`](../api/basic_json/to_ubjson.md) writes an array of these types without the `$` type annotation (the `#`
|
||||
count and one marker per element are kept) when it is longer, or when it would bring the total of the typed arrays
|
||||
written so far above 1,048,576, so everything it produces can be read back. Only input written by another encoder, or
|
||||
by version 3.12.0 and earlier of this library, can exceed the limit: for example, 1,100 rows of 1,000 `null` values or
|
||||
210,000 rows of 25, each with a `$Z` annotation. Version 3.12.0 writes such a row in 5 bytes (6 above 255 elements),
|
||||
so rows of 20 or fewer such values are never rejected.
|
||||
The exception is also thrown for a [UBJSON](../features/binary_formats/ubjson.md) array of a type that is encoded by its
|
||||
marker alone (`Z`, `T` or `F`) whose declared count exceeds 1,048,576 (`1 << 20`). Such an array has no payload, so its
|
||||
count alone decides how much memory is allocated, and a handful of bytes would otherwise describe billions of values.
|
||||
[`to_ubjson`](../api/basic_json/to_ubjson.md) writes longer arrays of these types without the `$` type annotation (the `#`
|
||||
count and one marker per element are kept), so any value it produces can still be read back.
|
||||
|
||||
!!! failure "Example messages"
|
||||
|
||||
@@ -1076,9 +1070,6 @@ so rows of 20 or fewer such values are never rejected.
|
||||
```
|
||||
[json.exception.out_of_range.408] syntax error while parsing UBJSON size: excessive array size
|
||||
```
|
||||
```
|
||||
[json.exception.out_of_range.408] syntax error while parsing UBJSON size: excessive number of elements without payload
|
||||
```
|
||||
|
||||
### json.exception.out_of_range.409
|
||||
|
||||
|
||||
@@ -73,46 +73,13 @@ the input.
|
||||
|
||||
This is a sanity bound rather than a security boundary, and it is far above
|
||||
any container met in practice. @ref binary_writer falls back to the
|
||||
unoptimized encoding for longer containers, and for containers that together
|
||||
with the ones before them would exceed @ref valueless_elements_base, so that a
|
||||
value serialized by this library can always be read back.
|
||||
unoptimized encoding for longer containers, so that a value serialized by
|
||||
this library can always be read back.
|
||||
|
||||
@sa https://github.com/nlohmann/json/issues/2793
|
||||
*/
|
||||
JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 20;
|
||||
|
||||
/*!
|
||||
@brief number of elements of valueless UBJSON containers accepted on top of
|
||||
@ref valueless_elements_per_byte
|
||||
|
||||
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
|
||||
9 bytes 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.
|
||||
*/
|
||||
JSON_INLINE_VARIABLE constexpr std::size_t valueless_elements_base = max_valueless_container_size;
|
||||
|
||||
/*!
|
||||
@brief number of elements of valueless UBJSON containers accepted per byte of
|
||||
input, in addition to @ref valueless_elements_base
|
||||
|
||||
An element of a value that has a payload costs at least one byte of input.
|
||||
Valueless elements are accepted at a rate of 4 per byte. A value takes 16
|
||||
bytes of memory in a DOM, so these arrays add about 80 bytes of memory per
|
||||
byte of input (measured: 77; one `Z` per byte needs about 32), beyond what the
|
||||
same bytes cost anyway, plus the base. This bounds the arrays of valueless
|
||||
type, not the memory of a whole document. Containers written by
|
||||
@ref binary_writer never need more than the base, because it writes an array
|
||||
in the unoptimized form once the typed arrays written so far and this one add
|
||||
up to more than that. The rate matters for input written by other encoders and
|
||||
by versions before 3.13.0 only; in the data this was measured on, no input has
|
||||
more than 0.17 elements per byte.
|
||||
*/
|
||||
JSON_INLINE_VARIABLE constexpr std::size_t valueless_elements_per_byte = 4;
|
||||
|
||||
///////////////////
|
||||
// binary reader //
|
||||
///////////////////
|
||||
@@ -3733,37 +3700,6 @@ class binary_reader
|
||||
return emit_unsigned(number);
|
||||
}
|
||||
|
||||
/*!
|
||||
@brief add the elements of a container of a valueless type to the total of
|
||||
the input and check the total against the input read so far
|
||||
|
||||
A container of type 'Z', 'T' or 'F' has no payload, so its elements are the
|
||||
only ones for which the input does not bound the count. The check is made
|
||||
once per container, not per element.
|
||||
|
||||
@param[in] count number of elements the container declares; at most
|
||||
@ref max_valueless_container_size
|
||||
@return false if the total is more than @ref valueless_elements_base plus
|
||||
@ref valueless_elements_per_byte for every byte read so far; the
|
||||
total is not changed then
|
||||
*/
|
||||
bool charge_valueless_elements(const std::size_t count) noexcept
|
||||
{
|
||||
// the limit saturates instead of overflowing when size_t is 32 bits
|
||||
// wide and a very large input has been read; valueless_elements
|
||||
// never exceeds the limit, so the difference cannot underflow
|
||||
constexpr std::size_t max_size = (std::numeric_limits<std::size_t>::max)();
|
||||
const std::size_t limit = chars_read <= (max_size - valueless_elements_base) / valueless_elements_per_byte
|
||||
? valueless_elements_base + (valueless_elements_per_byte * chars_read)
|
||||
: max_size;
|
||||
if (JSON_HEDLEY_UNLIKELY(count > limit - valueless_elements))
|
||||
{
|
||||
return false;
|
||||
}
|
||||
valueless_elements += count;
|
||||
return true;
|
||||
}
|
||||
|
||||
/*!
|
||||
@return whether array creation completed
|
||||
*/
|
||||
@@ -3849,27 +3785,24 @@ class binary_reader
|
||||
// declared count alone decides how much is allocated; the check is
|
||||
// made before the start event so that no container is opened that
|
||||
// is then abandoned. See @ref max_valueless_container_size.
|
||||
if (JSON_HEDLEY_UNLIKELY(size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F'))
|
||||
if (JSON_HEDLEY_UNLIKELY((size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F')
|
||||
&& size_and_type.first > max_valueless_container_size))
|
||||
{
|
||||
if (JSON_HEDLEY_UNLIKELY(size_and_type.first > max_valueless_container_size))
|
||||
{
|
||||
return out_of_range_error(exception_id::container_too_large, "excessive array size", "size");
|
||||
}
|
||||
if (JSON_HEDLEY_UNLIKELY(!charge_valueless_elements(size_and_type.first)))
|
||||
{
|
||||
return out_of_range_error(exception_id::container_too_large, "excessive number of elements without payload", "size");
|
||||
}
|
||||
return out_of_range_error(exception_id::container_too_large, "excessive array size", "size");
|
||||
}
|
||||
|
||||
// a no-op is not a value, so an array of them is empty whatever
|
||||
// count it declares: the SAX parser is told so, instead of being
|
||||
// made to reserve storage for a count that no input backs
|
||||
const std::size_t announced = size_and_type.second == 'N' ? 0 : size_and_type.first;
|
||||
if (JSON_HEDLEY_UNLIKELY(!enter_array(announced, size_and_type.second)))
|
||||
if (JSON_HEDLEY_UNLIKELY(!enter_array(size_and_type.first, size_and_type.second)))
|
||||
{
|
||||
return false;
|
||||
}
|
||||
|
||||
if (size_and_type.second == 'N')
|
||||
{
|
||||
// a no-op is not a value, so a container of them holds none;
|
||||
// the declared size has already been passed to the SAX parser
|
||||
container_stack.back().remaining = 0;
|
||||
}
|
||||
|
||||
return size_and_type.second == 0
|
||||
|| parse_ubjson_typed_run(container_stack.back().remaining, size_and_type.second, std::integral_constant<bool, bulk_scan> {});
|
||||
}
|
||||
@@ -5181,10 +5114,6 @@ class binary_reader
|
||||
/// the number of characters read
|
||||
std::size_t chars_read = 0;
|
||||
|
||||
/// UBJSON: the sum of the element counts of the containers of a valueless
|
||||
/// type read so far; see @ref charge_valueless_elements
|
||||
std::size_t valueless_elements = 0;
|
||||
|
||||
/// whether we can assume little endianness
|
||||
const bool is_little_endian = little_endianness();
|
||||
|
||||
|
||||
@@ -1091,6 +1091,32 @@ class json_pointer
|
||||
}
|
||||
};
|
||||
|
||||
/*!
|
||||
@brief the number of the deepest step of the previous path that is a prefix of the new one
|
||||
|
||||
Comparing every one of many steps with the beginning of the path would take
|
||||
quadratic time. Instead, the length of the common beginning of the two paths
|
||||
is computed once: a step whose prefix is not longer is a prefix of the new
|
||||
path, too. For few steps, which is the usual case, @ref resolve_plain
|
||||
compares them, which is cheaper.
|
||||
*/
|
||||
template<typename Steps>
|
||||
JSON_HEDLEY_NEVER_INLINE static std::size_t deepest_shared_step(const string_t& path, const std::size_t length, const string_t& previous, const Steps& steps) noexcept
|
||||
{
|
||||
const std::size_t same = common_prefix_length(path.data(), previous.data(), (std::min)(length, previous.size()));
|
||||
std::size_t depth = steps.size();
|
||||
for (; depth > 1; --depth)
|
||||
{
|
||||
// a step ends at a token boundary of the previous path
|
||||
const std::size_t prefix = steps[depth - 1].first;
|
||||
if (prefix <= same && (prefix == length || path[prefix] == '/'))
|
||||
{
|
||||
break;
|
||||
}
|
||||
}
|
||||
return depth;
|
||||
}
|
||||
|
||||
/*!
|
||||
@brief resolve a plain JSON pointer without building its reference tokens
|
||||
|
||||
@@ -1119,13 +1145,20 @@ class json_pointer
|
||||
if (cache.path != nullptr && !steps.empty() && steps[0].second == root)
|
||||
{
|
||||
const string_t& previous = *cache.path;
|
||||
for (depth = steps.size(); depth > 1; --depth)
|
||||
if (JSON_HEDLEY_UNLIKELY(steps.size() > 16))
|
||||
{
|
||||
// a step ends at a token boundary of the previous path
|
||||
const std::size_t prefix = steps[depth - 1].first;
|
||||
if (prefix <= length && (prefix == length || path[prefix] == '/') && std::memcmp(path.data(), previous.data(), prefix) == 0)
|
||||
depth = deepest_shared_step(path, length, previous, steps);
|
||||
}
|
||||
else
|
||||
{
|
||||
for (depth = steps.size(); depth > 1; --depth)
|
||||
{
|
||||
break;
|
||||
// a step ends at a token boundary of the previous path
|
||||
const std::size_t prefix = steps[depth - 1].first;
|
||||
if (prefix <= length && (prefix == length || path[prefix] == '/') && std::memcmp(path.data(), previous.data(), prefix) == 0)
|
||||
{
|
||||
break;
|
||||
}
|
||||
}
|
||||
}
|
||||
steps.resize(depth);
|
||||
|
||||
@@ -1204,27 +1204,20 @@ class binary_writer
|
||||
|
||||
// an optimized array of a valueless type carries no payload, so a
|
||||
// reader has nothing but the declared count to bound the allocation
|
||||
// by. It refuses one array of more than max_valueless_container_size
|
||||
// elements, and all such arrays of one input together when they add
|
||||
// up to more than valueless_elements_base plus a number per byte
|
||||
// read. Write the unoptimized form, at one byte per element, for
|
||||
// an array that would exceed the base with the arrays written so
|
||||
// far, so that the result can be read back: the limit of a reader
|
||||
// is never below the base. Objects are not affected: every element
|
||||
// is preceded by its key.
|
||||
if (same_prefix && !(use_bjdata && is_bjdata_excluded_type_marker(first_prefix)))
|
||||
// by and refuses an excessive one. Write the unoptimized form for
|
||||
// those, at one byte per element, so the result can be read back.
|
||||
// Objects are not affected: every element is preceded by its key.
|
||||
const bool valueless_type = (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
|
||||
const bool excessive_valueless = IsArray
|
||||
&& valueless_type
|
||||
&& size > detail::max_valueless_container_size;
|
||||
|
||||
if (same_prefix && !excessive_valueless
|
||||
&& !(use_bjdata && is_bjdata_excluded_type_marker(first_prefix)))
|
||||
{
|
||||
const bool valueless_type = IsArray && (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
|
||||
if (!valueless_type || size <= detail::valueless_elements_base - valueless_elements_written)
|
||||
{
|
||||
prefix_required = false;
|
||||
oa.write_character(to_char_type('$'));
|
||||
oa.write_character(first_prefix);
|
||||
if (valueless_type)
|
||||
{
|
||||
valueless_elements_written += size;
|
||||
}
|
||||
}
|
||||
prefix_required = false;
|
||||
oa.write_character(to_char_type('$'));
|
||||
oa.write_character(first_prefix);
|
||||
}
|
||||
}
|
||||
|
||||
@@ -5448,10 +5441,6 @@ class binary_writer
|
||||
/// how to treat a string value or object key that is not valid UTF-8
|
||||
/// (CBOR, MessagePack, UBJSON, BJData, and BSON; not BON8)
|
||||
const error_handler_t error_handler = binary_writer_default_error_handler();
|
||||
|
||||
/// UBJSON: the number of elements written so far in optimized arrays of a
|
||||
/// valueless type, which a reader adds up and bounds
|
||||
std::size_t valueless_elements_written = 0;
|
||||
};
|
||||
|
||||
} // namespace detail
|
||||
|
||||
Generated
+64
-113
@@ -18352,46 +18352,13 @@ the input.
|
||||
|
||||
This is a sanity bound rather than a security boundary, and it is far above
|
||||
any container met in practice. @ref binary_writer falls back to the
|
||||
unoptimized encoding for longer containers, and for containers that together
|
||||
with the ones before them would exceed @ref valueless_elements_base, so that a
|
||||
value serialized by this library can always be read back.
|
||||
unoptimized encoding for longer containers, so that a value serialized by
|
||||
this library can always be read back.
|
||||
|
||||
@sa https://github.com/nlohmann/json/issues/2793
|
||||
*/
|
||||
JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 20;
|
||||
|
||||
/*!
|
||||
@brief number of elements of valueless UBJSON containers accepted on top of
|
||||
@ref valueless_elements_per_byte
|
||||
|
||||
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
|
||||
9 bytes 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.
|
||||
*/
|
||||
JSON_INLINE_VARIABLE constexpr std::size_t valueless_elements_base = max_valueless_container_size;
|
||||
|
||||
/*!
|
||||
@brief number of elements of valueless UBJSON containers accepted per byte of
|
||||
input, in addition to @ref valueless_elements_base
|
||||
|
||||
An element of a value that has a payload costs at least one byte of input.
|
||||
Valueless elements are accepted at a rate of 4 per byte. A value takes 16
|
||||
bytes of memory in a DOM, so these arrays add about 80 bytes of memory per
|
||||
byte of input (measured: 77; one `Z` per byte needs about 32), beyond what the
|
||||
same bytes cost anyway, plus the base. This bounds the arrays of valueless
|
||||
type, not the memory of a whole document. Containers written by
|
||||
@ref binary_writer never need more than the base, because it writes an array
|
||||
in the unoptimized form once the typed arrays written so far and this one add
|
||||
up to more than that. The rate matters for input written by other encoders and
|
||||
by versions before 3.13.0 only; in the data this was measured on, no input has
|
||||
more than 0.17 elements per byte.
|
||||
*/
|
||||
JSON_INLINE_VARIABLE constexpr std::size_t valueless_elements_per_byte = 4;
|
||||
|
||||
///////////////////
|
||||
// binary reader //
|
||||
///////////////////
|
||||
@@ -22012,37 +21979,6 @@ class binary_reader
|
||||
return emit_unsigned(number);
|
||||
}
|
||||
|
||||
/*!
|
||||
@brief add the elements of a container of a valueless type to the total of
|
||||
the input and check the total against the input read so far
|
||||
|
||||
A container of type 'Z', 'T' or 'F' has no payload, so its elements are the
|
||||
only ones for which the input does not bound the count. The check is made
|
||||
once per container, not per element.
|
||||
|
||||
@param[in] count number of elements the container declares; at most
|
||||
@ref max_valueless_container_size
|
||||
@return false if the total is more than @ref valueless_elements_base plus
|
||||
@ref valueless_elements_per_byte for every byte read so far; the
|
||||
total is not changed then
|
||||
*/
|
||||
bool charge_valueless_elements(const std::size_t count) noexcept
|
||||
{
|
||||
// the limit saturates instead of overflowing when size_t is 32 bits
|
||||
// wide and a very large input has been read; valueless_elements
|
||||
// never exceeds the limit, so the difference cannot underflow
|
||||
constexpr std::size_t max_size = (std::numeric_limits<std::size_t>::max)();
|
||||
const std::size_t limit = chars_read <= (max_size - valueless_elements_base) / valueless_elements_per_byte
|
||||
? valueless_elements_base + (valueless_elements_per_byte * chars_read)
|
||||
: max_size;
|
||||
if (JSON_HEDLEY_UNLIKELY(count > limit - valueless_elements))
|
||||
{
|
||||
return false;
|
||||
}
|
||||
valueless_elements += count;
|
||||
return true;
|
||||
}
|
||||
|
||||
/*!
|
||||
@return whether array creation completed
|
||||
*/
|
||||
@@ -22128,27 +22064,24 @@ class binary_reader
|
||||
// declared count alone decides how much is allocated; the check is
|
||||
// made before the start event so that no container is opened that
|
||||
// is then abandoned. See @ref max_valueless_container_size.
|
||||
if (JSON_HEDLEY_UNLIKELY(size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F'))
|
||||
if (JSON_HEDLEY_UNLIKELY((size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F')
|
||||
&& size_and_type.first > max_valueless_container_size))
|
||||
{
|
||||
if (JSON_HEDLEY_UNLIKELY(size_and_type.first > max_valueless_container_size))
|
||||
{
|
||||
return out_of_range_error(exception_id::container_too_large, "excessive array size", "size");
|
||||
}
|
||||
if (JSON_HEDLEY_UNLIKELY(!charge_valueless_elements(size_and_type.first)))
|
||||
{
|
||||
return out_of_range_error(exception_id::container_too_large, "excessive number of elements without payload", "size");
|
||||
}
|
||||
return out_of_range_error(exception_id::container_too_large, "excessive array size", "size");
|
||||
}
|
||||
|
||||
// a no-op is not a value, so an array of them is empty whatever
|
||||
// count it declares: the SAX parser is told so, instead of being
|
||||
// made to reserve storage for a count that no input backs
|
||||
const std::size_t announced = size_and_type.second == 'N' ? 0 : size_and_type.first;
|
||||
if (JSON_HEDLEY_UNLIKELY(!enter_array(announced, size_and_type.second)))
|
||||
if (JSON_HEDLEY_UNLIKELY(!enter_array(size_and_type.first, size_and_type.second)))
|
||||
{
|
||||
return false;
|
||||
}
|
||||
|
||||
if (size_and_type.second == 'N')
|
||||
{
|
||||
// a no-op is not a value, so a container of them holds none;
|
||||
// the declared size has already been passed to the SAX parser
|
||||
container_stack.back().remaining = 0;
|
||||
}
|
||||
|
||||
return size_and_type.second == 0
|
||||
|| parse_ubjson_typed_run(container_stack.back().remaining, size_and_type.second, std::integral_constant<bool, bulk_scan> {});
|
||||
}
|
||||
@@ -23460,10 +23393,6 @@ class binary_reader
|
||||
/// the number of characters read
|
||||
std::size_t chars_read = 0;
|
||||
|
||||
/// UBJSON: the sum of the element counts of the containers of a valueless
|
||||
/// type read so far; see @ref charge_valueless_elements
|
||||
std::size_t valueless_elements = 0;
|
||||
|
||||
/// whether we can assume little endianness
|
||||
const bool is_little_endian = little_endianness();
|
||||
|
||||
@@ -27337,6 +27266,32 @@ class json_pointer
|
||||
}
|
||||
};
|
||||
|
||||
/*!
|
||||
@brief the number of the deepest step of the previous path that is a prefix of the new one
|
||||
|
||||
Comparing every one of many steps with the beginning of the path would take
|
||||
quadratic time. Instead, the length of the common beginning of the two paths
|
||||
is computed once: a step whose prefix is not longer is a prefix of the new
|
||||
path, too. For few steps, which is the usual case, @ref resolve_plain
|
||||
compares them, which is cheaper.
|
||||
*/
|
||||
template<typename Steps>
|
||||
JSON_HEDLEY_NEVER_INLINE static std::size_t deepest_shared_step(const string_t& path, const std::size_t length, const string_t& previous, const Steps& steps) noexcept
|
||||
{
|
||||
const std::size_t same = common_prefix_length(path.data(), previous.data(), (std::min)(length, previous.size()));
|
||||
std::size_t depth = steps.size();
|
||||
for (; depth > 1; --depth)
|
||||
{
|
||||
// a step ends at a token boundary of the previous path
|
||||
const std::size_t prefix = steps[depth - 1].first;
|
||||
if (prefix <= same && (prefix == length || path[prefix] == '/'))
|
||||
{
|
||||
break;
|
||||
}
|
||||
}
|
||||
return depth;
|
||||
}
|
||||
|
||||
/*!
|
||||
@brief resolve a plain JSON pointer without building its reference tokens
|
||||
|
||||
@@ -27365,13 +27320,20 @@ class json_pointer
|
||||
if (cache.path != nullptr && !steps.empty() && steps[0].second == root)
|
||||
{
|
||||
const string_t& previous = *cache.path;
|
||||
for (depth = steps.size(); depth > 1; --depth)
|
||||
if (JSON_HEDLEY_UNLIKELY(steps.size() > 16))
|
||||
{
|
||||
// a step ends at a token boundary of the previous path
|
||||
const std::size_t prefix = steps[depth - 1].first;
|
||||
if (prefix <= length && (prefix == length || path[prefix] == '/') && std::memcmp(path.data(), previous.data(), prefix) == 0)
|
||||
depth = deepest_shared_step(path, length, previous, steps);
|
||||
}
|
||||
else
|
||||
{
|
||||
for (depth = steps.size(); depth > 1; --depth)
|
||||
{
|
||||
break;
|
||||
// a step ends at a token boundary of the previous path
|
||||
const std::size_t prefix = steps[depth - 1].first;
|
||||
if (prefix <= length && (prefix == length || path[prefix] == '/') && std::memcmp(path.data(), previous.data(), prefix) == 0)
|
||||
{
|
||||
break;
|
||||
}
|
||||
}
|
||||
}
|
||||
steps.resize(depth);
|
||||
@@ -30617,27 +30579,20 @@ class binary_writer
|
||||
|
||||
// an optimized array of a valueless type carries no payload, so a
|
||||
// reader has nothing but the declared count to bound the allocation
|
||||
// by. It refuses one array of more than max_valueless_container_size
|
||||
// elements, and all such arrays of one input together when they add
|
||||
// up to more than valueless_elements_base plus a number per byte
|
||||
// read. Write the unoptimized form, at one byte per element, for
|
||||
// an array that would exceed the base with the arrays written so
|
||||
// far, so that the result can be read back: the limit of a reader
|
||||
// is never below the base. Objects are not affected: every element
|
||||
// is preceded by its key.
|
||||
if (same_prefix && !(use_bjdata && is_bjdata_excluded_type_marker(first_prefix)))
|
||||
// by and refuses an excessive one. Write the unoptimized form for
|
||||
// those, at one byte per element, so the result can be read back.
|
||||
// Objects are not affected: every element is preceded by its key.
|
||||
const bool valueless_type = (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
|
||||
const bool excessive_valueless = IsArray
|
||||
&& valueless_type
|
||||
&& size > detail::max_valueless_container_size;
|
||||
|
||||
if (same_prefix && !excessive_valueless
|
||||
&& !(use_bjdata && is_bjdata_excluded_type_marker(first_prefix)))
|
||||
{
|
||||
const bool valueless_type = IsArray && (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
|
||||
if (!valueless_type || size <= detail::valueless_elements_base - valueless_elements_written)
|
||||
{
|
||||
prefix_required = false;
|
||||
oa.write_character(to_char_type('$'));
|
||||
oa.write_character(first_prefix);
|
||||
if (valueless_type)
|
||||
{
|
||||
valueless_elements_written += size;
|
||||
}
|
||||
}
|
||||
prefix_required = false;
|
||||
oa.write_character(to_char_type('$'));
|
||||
oa.write_character(first_prefix);
|
||||
}
|
||||
}
|
||||
|
||||
@@ -34861,10 +34816,6 @@ class binary_writer
|
||||
/// how to treat a string value or object key that is not valid UTF-8
|
||||
/// (CBOR, MessagePack, UBJSON, BJData, and BSON; not BON8)
|
||||
const error_handler_t error_handler = binary_writer_default_error_handler();
|
||||
|
||||
/// UBJSON: the number of elements written so far in optimized arrays of a
|
||||
/// valueless type, which a reader adds up and bounds
|
||||
std::size_t valueless_elements_written = 0;
|
||||
};
|
||||
|
||||
} // namespace detail
|
||||
|
||||
@@ -14,9 +14,12 @@ using nlohmann::json;
|
||||
using namespace nlohmann::literals; // NOLINT(google-build-using-namespace)
|
||||
#endif
|
||||
|
||||
#include <algorithm>
|
||||
#include <cstddef>
|
||||
#include <ctime>
|
||||
#include <fstream>
|
||||
#include <limits>
|
||||
#include <random>
|
||||
#include <string>
|
||||
#include <utility>
|
||||
#include <vector>
|
||||
@@ -2551,3 +2554,419 @@ TEST_CASE("JSON patch - diff of leaf values below the bound of the recursive des
|
||||
CHECK(object_patch.size() == 2);
|
||||
CHECK(object_source.patch(object_patch) == object_target);
|
||||
}
|
||||
|
||||
namespace
|
||||
{
|
||||
// all pointers to values below `value` (not to `value` itself)
|
||||
void collect_pointers(const json& value, const std::string& path, std::vector<std::string>& pointers)
|
||||
{
|
||||
if (value.is_object())
|
||||
{
|
||||
for (const auto& element : value.items())
|
||||
{
|
||||
std::string child = path;
|
||||
child += '/';
|
||||
for (const char c : element.key())
|
||||
{
|
||||
if (c == '~')
|
||||
{
|
||||
child += "~0";
|
||||
}
|
||||
else if (c == '/')
|
||||
{
|
||||
child += "~1";
|
||||
}
|
||||
else
|
||||
{
|
||||
child += c;
|
||||
}
|
||||
}
|
||||
pointers.push_back(child);
|
||||
collect_pointers(element.value(), child, pointers);
|
||||
}
|
||||
}
|
||||
else if (value.is_array())
|
||||
{
|
||||
for (std::size_t i = 0; i < value.size(); ++i)
|
||||
{
|
||||
std::string child = path;
|
||||
child += '/';
|
||||
child += std::to_string(i);
|
||||
pointers.push_back(child);
|
||||
collect_pointers(value[i], child, pointers);
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// a random document of at most `depth` levels, with the names as keys
|
||||
json random_document(std::mt19937& gen, const std::vector<std::string>& names, const int depth)
|
||||
{
|
||||
const int kind = std::uniform_int_distribution<int>(0, 9)(gen);
|
||||
if (depth == 0 || kind < 2)
|
||||
{
|
||||
return std::uniform_int_distribution<int>(0, 3)(gen);
|
||||
}
|
||||
const int size = std::uniform_int_distribution<int>(1, 3)(gen);
|
||||
json result = kind < 6 ? json::array() : json::object();
|
||||
for (int i = 0; i < size; ++i)
|
||||
{
|
||||
if (kind < 6)
|
||||
{
|
||||
result.push_back(random_document(gen, names, depth - 1));
|
||||
}
|
||||
else
|
||||
{
|
||||
result[names[std::uniform_int_distribution<std::size_t>(0, names.size() - 1)(gen)]] = random_document(gen, names, depth - 1);
|
||||
}
|
||||
}
|
||||
return result;
|
||||
}
|
||||
|
||||
// the strings, one after the other
|
||||
std::string concat(std::string first, const std::string& second, const std::string& third = std::string())
|
||||
{
|
||||
first += second;
|
||||
first += third;
|
||||
return first;
|
||||
}
|
||||
|
||||
// the best of five times in seconds that std::clock() measures to apply the patch
|
||||
double patch_cpu_time(json& doc, const json& patch)
|
||||
{
|
||||
double best = 1e30;
|
||||
for (int i = 0; i < 5; ++i)
|
||||
{
|
||||
const std::clock_t start = std::clock();
|
||||
doc.patch_inplace(patch);
|
||||
best = (std::min)(best, static_cast<double>(std::clock() - start) / static_cast<double>(CLOCKS_PER_SEC));
|
||||
}
|
||||
return best;
|
||||
}
|
||||
} // namespace
|
||||
|
||||
TEST_CASE("JSON patch - consecutive operations with paths that share a prefix")
|
||||
{
|
||||
SECTION("tokens that start the same way")
|
||||
{
|
||||
const json doc = {{"a", {{"bc", {{"x", 1}}}, {"b", {{"x", 2}}}, {"b2", 3}}}};
|
||||
|
||||
// the second path shares "/a/b" with the first, but not the token "bc"
|
||||
const json patch = json::parse(R"([
|
||||
{"op": "test", "path": "/a/bc/x", "value": 1},
|
||||
{"op": "test", "path": "/a/b/x", "value": 2},
|
||||
{"op": "test", "path": "/a/bc/x", "value": 1},
|
||||
{"op": "test", "path": "/a/b2", "value": 3},
|
||||
{"op": "test", "path": "/a/b/x", "value": 2}
|
||||
])");
|
||||
CHECK(doc.patch(patch) == doc);
|
||||
|
||||
json inplace = doc;
|
||||
inplace.patch_inplace(patch);
|
||||
CHECK(inplace == doc);
|
||||
|
||||
// a path that is a prefix of the previous one, and the other way round
|
||||
const json prefixes = json::parse(R"([
|
||||
{"op": "test", "path": "/a/bc/x", "value": 1},
|
||||
{"op": "test", "path": "/a/bc", "value": {"x": 1}},
|
||||
{"op": "test", "path": "/a/bc/x", "value": 1},
|
||||
{"op": "test", "path": "/a", "value": {"bc": {"x": 1}, "b": {"x": 2}, "b2": 3}},
|
||||
{"op": "test", "path": "/a/b/x", "value": 2},
|
||||
{"op": "test", "path": "", "value": {"a": {"bc": {"x": 1}, "b": {"x": 2}, "b2": 3}}}
|
||||
])");
|
||||
CHECK(doc.patch(prefixes) == doc);
|
||||
}
|
||||
|
||||
SECTION("operations above a path that was resolved before")
|
||||
{
|
||||
const json doc = json::parse(R"({"a": [{"b": [1, 2, 3]}, {"b": [4, 5, 6]}], "c": {"d": {"e": 7}}})");
|
||||
|
||||
// an element inserted before the elements of an array moves them
|
||||
CHECK(doc.patch(json::parse(R"([
|
||||
{"op": "test", "path": "/a/0/b/2", "value": 3},
|
||||
{"op": "add", "path": "/a/0", "value": {"b": [9]}},
|
||||
{"op": "test", "path": "/a/1/b/2", "value": 3},
|
||||
{"op": "test", "path": "/a/0/b/0", "value": 9},
|
||||
{"op": "test", "path": "/a/2/b/0", "value": 4}
|
||||
])")) == json::parse(R"({"a": [{"b": [9]}, {"b": [1, 2, 3]}, {"b": [4, 5, 6]}], "c": {"d": {"e": 7}}})"));
|
||||
|
||||
// an element removed from the front
|
||||
CHECK(doc.patch(json::parse(R"([
|
||||
{"op": "test", "path": "/a/1/b/2", "value": 6},
|
||||
{"op": "remove", "path": "/a/0"},
|
||||
{"op": "test", "path": "/a/0/b/2", "value": 6},
|
||||
{"op": "replace", "path": "/a/0/b/2", "value": 60},
|
||||
{"op": "test", "path": "/a/0/b/2", "value": 60}
|
||||
])")) == json::parse(R"({"a": [{"b": [4, 5, 60]}], "c": {"d": {"e": 7}}})"));
|
||||
|
||||
// a value replaced above the path that was resolved before
|
||||
CHECK(doc.patch(json::parse(R"([
|
||||
{"op": "test", "path": "/c/d/e", "value": 7},
|
||||
{"op": "replace", "path": "/c/d", "value": {"e": 8, "f": {"g": 9}}},
|
||||
{"op": "test", "path": "/c/d/e", "value": 8},
|
||||
{"op": "test", "path": "/c/d/f/g", "value": 9},
|
||||
{"op": "remove", "path": "/c/d/f"},
|
||||
{"op": "add", "path": "/c/d/f", "value": [1]},
|
||||
{"op": "test", "path": "/c/d/f/0", "value": 1}
|
||||
])")) == json::parse(R"({"a": [{"b": [1, 2, 3]}, {"b": [4, 5, 6]}], "c": {"d": {"e": 8, "f": [1]}}})"));
|
||||
|
||||
#if !defined(JSON_NOEXCEPTION)
|
||||
// a value removed above the path that was resolved before is gone
|
||||
const json removed = json::parse(R"([
|
||||
{"op": "test", "path": "/c/d/e", "value": 7},
|
||||
{"op": "remove", "path": "/c/d"},
|
||||
{"op": "test", "path": "/c/d/e", "value": 7}
|
||||
])");
|
||||
CHECK_THROWS_AS(doc.patch(removed), json::other_error&);
|
||||
json inplace = doc;
|
||||
CHECK_THROWS_AS(inplace.patch_inplace(removed), json::other_error&);
|
||||
|
||||
const json emptied = json::parse(R"([
|
||||
{"op": "test", "path": "/a/1/b/2", "value": 6},
|
||||
{"op": "remove", "path": "/a/1"},
|
||||
{"op": "test", "path": "/a/1/b/2", "value": 6}
|
||||
])");
|
||||
CHECK_THROWS_AS(doc.patch(emptied), json::other_error&);
|
||||
#endif
|
||||
}
|
||||
|
||||
SECTION("paths with more than 16 tokens")
|
||||
{
|
||||
// 40 levels, with an array at the bottom and a second branch at level 20
|
||||
std::string prefix20;
|
||||
std::string prefix40;
|
||||
json doc = {{"leaf", {1, 2, 3}}};
|
||||
for (int i = 40; i > 0; --i)
|
||||
{
|
||||
if (i == 20)
|
||||
{
|
||||
doc["other"] = {{"x", 5}};
|
||||
}
|
||||
doc = {{"n", doc}};
|
||||
}
|
||||
for (int i = 1; i <= 40; ++i)
|
||||
{
|
||||
prefix40 += "/n";
|
||||
if (i == 20)
|
||||
{
|
||||
prefix20 = prefix40;
|
||||
}
|
||||
}
|
||||
|
||||
const auto op = [](const char* name, const std::string & path, const json & value)
|
||||
{
|
||||
return json({{"op", name}, {"path", path}, {"value", value}});
|
||||
};
|
||||
const json patch =
|
||||
{
|
||||
op("test", concat(prefix40, "/leaf/2"), 3),
|
||||
op("test", concat(prefix20, "/other/x"), 5),
|
||||
op("test", concat(prefix40, "/leaf/0"), 1),
|
||||
op("add", concat(prefix40, "/leaf/0"), 0),
|
||||
op("test", concat(prefix40, "/leaf/3"), 3),
|
||||
op("replace", concat(prefix20, "/other"), {{"x", 6}}),
|
||||
op("test", concat(prefix20, "/other/x"), 6),
|
||||
op("test", concat(prefix40, "/leaf/1"), 1),
|
||||
{{"op", "remove"}, {"path", concat(prefix20, "/other")}},
|
||||
op("test", concat(prefix40, "/leaf/1"), 1)
|
||||
};
|
||||
json expected = doc;
|
||||
for (const auto& operation : patch)
|
||||
{
|
||||
expected = expected.patch(json::array({operation}));
|
||||
}
|
||||
CHECK(doc.patch(patch) == expected);
|
||||
json inplace = doc;
|
||||
inplace.patch_inplace(patch);
|
||||
CHECK(inplace == expected);
|
||||
CHECK(expected[json::json_pointer(concat(prefix40, "/leaf"))] == json({0, 1, 2, 3}));
|
||||
CHECK(!expected[json::json_pointer(prefix20)].contains("other"));
|
||||
|
||||
#if !defined(JSON_NOEXCEPTION)
|
||||
// the value that was resolved before is gone with the member that held it
|
||||
const json gone =
|
||||
{
|
||||
op("test", concat(prefix40, "/leaf/2"), 3),
|
||||
{{"op", "remove"}, {"path", prefix20}},
|
||||
op("test", concat(prefix40, "/leaf/2"), 3)
|
||||
};
|
||||
CHECK_THROWS_AS(doc.patch(gone), json::other_error&);
|
||||
#endif
|
||||
}
|
||||
|
||||
SECTION("random sequences of operations give the same result as one operation at a time")
|
||||
{
|
||||
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", "abc", "a/b", "a~b", "1", "10", "token_longer_than_eight_bytes"};
|
||||
const auto pick = [&gen](const std::size_t n)
|
||||
{
|
||||
return std::uniform_int_distribution<std::size_t>(0, n - 1)(gen);
|
||||
};
|
||||
|
||||
for (int round = 0; round < 300; ++round)
|
||||
{
|
||||
const json start = random_document(gen, names, 7);
|
||||
json current = start;
|
||||
json patch = json::array();
|
||||
std::string previous;
|
||||
|
||||
for (int step = 0; step < 25; ++step)
|
||||
{
|
||||
std::vector<std::string> pointers;
|
||||
collect_pointers(current, "", pointers);
|
||||
if (pointers.empty())
|
||||
{
|
||||
break;
|
||||
}
|
||||
|
||||
// most of the time, stay below a part of the previous path
|
||||
std::vector<std::string> candidates;
|
||||
if (!previous.empty() && pick(10) < 8)
|
||||
{
|
||||
std::string prefix = previous;
|
||||
const std::size_t cut = prefix.find('/', 1 + pick(prefix.size()));
|
||||
prefix = prefix.substr(0, cut == std::string::npos ? prefix.size() : cut);
|
||||
for (const auto& p : pointers)
|
||||
{
|
||||
if (p.compare(0, prefix.size(), prefix) == 0)
|
||||
{
|
||||
candidates.push_back(p);
|
||||
}
|
||||
}
|
||||
}
|
||||
if (candidates.empty())
|
||||
{
|
||||
candidates = pointers;
|
||||
}
|
||||
const std::string path = candidates[pick(candidates.size())];
|
||||
const json::json_pointer pointer(path);
|
||||
|
||||
json operation;
|
||||
switch (pick(5))
|
||||
{
|
||||
case 0:
|
||||
operation = {{"op", "test"}, {"path", path}, {"value", current[pointer]}};
|
||||
break;
|
||||
case 1:
|
||||
operation = {{"op", "replace"}, {"path", path}, {"value", static_cast<int>(pick(100))}};
|
||||
break;
|
||||
case 2:
|
||||
operation = {{"op", "remove"}, {"path", path}};
|
||||
break;
|
||||
default:
|
||||
{
|
||||
// add below an array or object, which may be the root
|
||||
const json::json_pointer parent_pointer = pick(4) == 0 ? json::json_pointer() : pointer;
|
||||
const std::string parent_path = parent_pointer.to_string();
|
||||
const json& parent = current[parent_pointer];
|
||||
std::string token = "-";
|
||||
if (parent.is_array())
|
||||
{
|
||||
token = pick(3) == 0 ? "-" : std::to_string(pick(parent.size() + 1));
|
||||
}
|
||||
else if (parent.is_object())
|
||||
{
|
||||
token = pick(2) == 0 ? "new" : "ab";
|
||||
}
|
||||
else
|
||||
{
|
||||
// a primitive parent: replace it instead
|
||||
operation = {{"op", "replace"}, {"path", parent_path}, {"value", json::array({1, 2})}};
|
||||
break;
|
||||
}
|
||||
operation = {{"op", "add"}, {"path", concat(parent_path, "/", token)}, {"value", json::object({{"k", {1, 2}}})}};
|
||||
break;
|
||||
}
|
||||
}
|
||||
if (operation["path"].get<std::string>().empty())
|
||||
{
|
||||
continue;
|
||||
}
|
||||
|
||||
// one operation at a time: the cache is empty at the start of each
|
||||
current = current.patch(json::array({operation}));
|
||||
patch.push_back(operation);
|
||||
previous = operation["path"].get<std::string>();
|
||||
}
|
||||
|
||||
CHECK(start.patch(patch) == current);
|
||||
json inplace = start;
|
||||
inplace.patch_inplace(patch);
|
||||
CHECK(inplace == current);
|
||||
|
||||
// the same for a type that keeps the order of the members, which makes
|
||||
// objects that were built in a different order unequal: leave out the
|
||||
// tests of structured values
|
||||
json without_tests = json::array();
|
||||
for (const auto& operation : patch)
|
||||
{
|
||||
if (operation["op"] != "test" || !operation["value"].is_structured())
|
||||
{
|
||||
without_tests.push_back(operation);
|
||||
}
|
||||
}
|
||||
const nlohmann::ordered_json ordered_patch = without_tests;
|
||||
nlohmann::ordered_json ordered_inplace = start;
|
||||
ordered_inplace.patch_inplace(ordered_patch);
|
||||
CHECK(json(ordered_inplace) == current);
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
TEST_CASE("JSON patch - time is linear for long paths that share a prefix")
|
||||
{
|
||||
// The time of the patch is compared with the time of a patch that is
|
||||
// linear for sure, because a bound in seconds would depend on the machine:
|
||||
// both test the same two values at the end of paths with 2n tokens. The
|
||||
// second path of the first patch shares n tokens with the first one and
|
||||
// continues for n tokens: the ratio is 1 to 2, and about 60 when every
|
||||
// step is compared with the start of the path. 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).
|
||||
constexpr std::size_t n = 25000;
|
||||
|
||||
const auto nest = [](const std::size_t depth, const std::string & inner)
|
||||
{
|
||||
std::string text;
|
||||
for (std::size_t i = 0; i < depth; ++i)
|
||||
{
|
||||
text += "{\"a\":";
|
||||
}
|
||||
text += inner;
|
||||
text.append(depth, '}');
|
||||
return text;
|
||||
};
|
||||
std::string as;
|
||||
for (std::size_t i = 0; i < n; ++i)
|
||||
{
|
||||
as += "/a";
|
||||
}
|
||||
const std::string deep = nest(n, "1");
|
||||
std::string members = "{\"x\":";
|
||||
members += deep;
|
||||
members += ",\"y\":";
|
||||
members += deep;
|
||||
members += "}";
|
||||
json doc = json::parse(nest(n, members));
|
||||
|
||||
const auto test_op = [](const std::string & path)
|
||||
{
|
||||
return json({{"op", "test"}, {"path", path}, {"value", 1}});
|
||||
};
|
||||
const json shared = json::array({test_op(concat(as, "/x", as)), test_op(concat(as, "/y", as))});
|
||||
const json same = json::array({test_op(concat(as, "/x", as)), test_op(concat(as, "/x", as))});
|
||||
|
||||
// the operations do not change the document, which is too deep to copy;
|
||||
// a busy machine may spoil one comparison, hardly two
|
||||
bool linear = false;
|
||||
double t_shared = 0;
|
||||
double t_same = 0;
|
||||
for (int attempt = 0; attempt < 2 && !linear; ++attempt)
|
||||
{
|
||||
t_shared = patch_cpu_time(doc, shared);
|
||||
t_same = (std::max)(patch_cpu_time(doc, same), 1e-3);
|
||||
linear = t_shared < 10 * t_same;
|
||||
}
|
||||
CAPTURE(t_shared)
|
||||
CAPTURE(t_same)
|
||||
CHECK(linear);
|
||||
}
|
||||
@@ -19,12 +19,8 @@
|
||||
#include <nlohmann/json.hpp>
|
||||
using nlohmann::json;
|
||||
|
||||
#include <cstdio>
|
||||
#include <iostream>
|
||||
#include <sstream>
|
||||
#include <utility>
|
||||
#include <fstream>
|
||||
#include <limits>
|
||||
#include <list>
|
||||
#include <set>
|
||||
#include "make_test_data_available.hpp"
|
||||
@@ -2440,341 +2436,6 @@ TEST_CASE("UBJSON optimized arrays of a valueless type are bounded")
|
||||
}
|
||||
}
|
||||
|
||||
namespace
|
||||
{
|
||||
/// SAX consumer that counts the values and keeps the id of a parse error
|
||||
struct ValuelessEventCounter : public nlohmann::json_sax<json>
|
||||
{
|
||||
bool null() override
|
||||
{
|
||||
return ++values < stop_after;
|
||||
}
|
||||
bool boolean(bool /*val*/) override
|
||||
{
|
||||
return ++values < stop_after;
|
||||
}
|
||||
bool number_integer(json::number_integer_t /*val*/) override
|
||||
{
|
||||
++values;
|
||||
return true;
|
||||
}
|
||||
bool number_unsigned(json::number_unsigned_t /*val*/) override
|
||||
{
|
||||
++values;
|
||||
return true;
|
||||
}
|
||||
bool number_float(json::number_float_t /*val*/, const std::string& /*s*/) override
|
||||
{
|
||||
++values;
|
||||
return true;
|
||||
}
|
||||
bool string(std::string& /*val*/) override
|
||||
{
|
||||
++values;
|
||||
return true;
|
||||
}
|
||||
bool binary(json::binary_t& /*val*/) override
|
||||
{
|
||||
++values;
|
||||
return true;
|
||||
}
|
||||
bool start_object(std::size_t /*elements*/) override
|
||||
{
|
||||
return true;
|
||||
}
|
||||
bool key(std::string& /*val*/) override
|
||||
{
|
||||
return true;
|
||||
}
|
||||
bool end_object() override
|
||||
{
|
||||
return true;
|
||||
}
|
||||
bool start_array(std::size_t /*elements*/) override
|
||||
{
|
||||
return true;
|
||||
}
|
||||
bool end_array() override
|
||||
{
|
||||
return true;
|
||||
}
|
||||
bool parse_error(std::size_t /*position*/, const std::string& /*last_token*/, const json::exception& ex) override
|
||||
{
|
||||
error_id = ex.id;
|
||||
return false;
|
||||
}
|
||||
|
||||
/// the handler refuses the value that makes this many
|
||||
std::size_t stop_after = (std::numeric_limits<std::size_t>::max)();
|
||||
std::size_t values = 0;
|
||||
int error_id = 0;
|
||||
};
|
||||
|
||||
/// appends `[$<marker>#l<count>` (nine bytes) to @a v
|
||||
void append_valueless_array(std::vector<std::uint8_t>& v, const char marker, const std::uint32_t count)
|
||||
{
|
||||
v.push_back('[');
|
||||
v.push_back('$');
|
||||
v.push_back(static_cast<std::uint8_t>(marker));
|
||||
v.push_back('#');
|
||||
v.push_back('l');
|
||||
v.push_back(static_cast<std::uint8_t>(count >> 24));
|
||||
v.push_back(static_cast<std::uint8_t>(count >> 16));
|
||||
v.push_back(static_cast<std::uint8_t>(count >> 8));
|
||||
v.push_back(static_cast<std::uint8_t>(count));
|
||||
}
|
||||
|
||||
/// `[` followed by one `[$<marker>#l<count>` per entry of @a counts and `]`
|
||||
std::vector<std::uint8_t> valueless_arrays(const char marker, const std::vector<std::uint32_t>& counts)
|
||||
{
|
||||
std::vector<std::uint8_t> v = {'['};
|
||||
for (const auto count : counts)
|
||||
{
|
||||
append_valueless_array(v, marker, count);
|
||||
}
|
||||
v.push_back(']');
|
||||
return v;
|
||||
}
|
||||
} // namespace
|
||||
|
||||
TEST_CASE("UBJSON the valueless elements of a whole input are bounded")
|
||||
{
|
||||
// The per-container limit alone let nine bytes (`[$Z#l` and a count of
|
||||
// 1048576) announce a million values, and every further nine bytes another
|
||||
// million. The elements of all containers of type 'Z', 'T' or 'F' in one
|
||||
// input are now added up: they may not exceed 1048576 plus 4 for every
|
||||
// byte read when the container's header has been read.
|
||||
//
|
||||
// The tests count events with a SAX handler where they can: building and
|
||||
// comparing values of a million elements is what makes them slow under
|
||||
// Valgrind, so there is one rejection and one round trip with a DOM.
|
||||
json _;
|
||||
const char* const budget_message = "[json.exception.out_of_range.408] syntax error while parsing UBJSON size: excessive number of elements without payload";
|
||||
|
||||
// two arrays that exceed the limit: the second one, with its header read
|
||||
// at byte 19, may hold 4 * 19 = 76 values on top of the base of 1048576
|
||||
const std::uint32_t over_first = 524288;
|
||||
const std::uint32_t over_second = 1048576 + 76 - over_first + 1;
|
||||
|
||||
SECTION("the input of the original report is rejected")
|
||||
{
|
||||
// 362 bytes (40 arrays of 1048576 values) used to allocate 661 MB; the
|
||||
// second array is the one that is refused
|
||||
const auto input = valueless_arrays('Z', {over_first, over_second});
|
||||
CHECK_THROWS_WITH_AS(_ = json::from_ubjson(input), budget_message, json::out_of_range&);
|
||||
}
|
||||
|
||||
SECTION("every input adapter applies the budget")
|
||||
{
|
||||
const auto input = valueless_arrays('Z', {over_first, over_second});
|
||||
|
||||
// stream; not strict, which does not matter
|
||||
std::stringstream stream;
|
||||
stream.write(reinterpret_cast<const char*>(input.data()), static_cast<std::streamsize>(input.size()));
|
||||
ValuelessEventCounter from_stream;
|
||||
CHECK(!json::sax_parse(stream, &from_stream, json::input_format_t::ubjson, false));
|
||||
CHECK(from_stream.error_id == 408);
|
||||
|
||||
// a container that is not contiguous; the counts of arrays of
|
||||
// different types are added up
|
||||
std::vector<std::uint8_t> mixed = {'['};
|
||||
append_valueless_array(mixed, 'T', over_first);
|
||||
append_valueless_array(mixed, 'F', over_second);
|
||||
mixed.push_back(']');
|
||||
const std::list<std::uint8_t> as_list(mixed.begin(), mixed.end());
|
||||
ValuelessEventCounter from_list;
|
||||
CHECK(!json::sax_parse(as_list.begin(), as_list.end(), &from_list, json::input_format_t::ubjson));
|
||||
CHECK(from_list.error_id == 408);
|
||||
CHECK(from_list.values == over_first);
|
||||
|
||||
// FILE*
|
||||
FILE* const file = std::tmpfile(); // NOLINT(cppcoreguidelines-owning-memory)
|
||||
REQUIRE(file != nullptr);
|
||||
CHECK(std::fwrite(input.data(), 1, input.size(), file) == input.size());
|
||||
std::rewind(file);
|
||||
ValuelessEventCounter from_file;
|
||||
CHECK(!json::sax_parse(file, &from_file, json::input_format_t::ubjson));
|
||||
CHECK(from_file.error_id == 408);
|
||||
std::fclose(file); // NOLINT(cert-err33-c,cppcoreguidelines-owning-memory)
|
||||
}
|
||||
|
||||
SECTION("the limit is exact and the bytes read raise it")
|
||||
{
|
||||
// [ [$Z#l 524288] [$U#l 4096 + 4096 bytes] [$Z#l count] ]: chars_read
|
||||
// is 1 + 9 + (9 + 4096) + 9 = 4124 when the last header has been read,
|
||||
// so the last array may hold 4 * 4124 = 16496 values on top of the
|
||||
// base of 1048576 less the 524288 of the first array
|
||||
const std::uint32_t last_allowed = 1048576 + 16496 - 524288;
|
||||
for (const std::uint32_t count :
|
||||
{
|
||||
last_allowed, last_allowed + 1
|
||||
})
|
||||
{
|
||||
CAPTURE(count)
|
||||
std::vector<std::uint8_t> input = {'['};
|
||||
append_valueless_array(input, 'Z', 524288);
|
||||
input.insert(input.end(), {'[', '$', 'U', '#', 'l', 0x00, 0x00, 0x10, 0x00});
|
||||
input.insert(input.end(), 4096, 0x01);
|
||||
append_valueless_array(input, 'Z', count);
|
||||
input.push_back(']');
|
||||
ValuelessEventCounter sax;
|
||||
const bool accepted = count == last_allowed;
|
||||
CHECK(json::sax_parse(input, &sax, json::input_format_t::ubjson) == accepted);
|
||||
CHECK(sax.error_id == (accepted ? 0 : 408));
|
||||
CHECK(sax.values == 524288u + 4096u + (accepted ? count : 0u));
|
||||
}
|
||||
|
||||
// an array of 1048576 values on its own is accepted as before
|
||||
const std::vector<std::uint8_t> single = {'[', '$', 'Z', '#', 'l', 0x00, 0x10, 0x00, 0x00};
|
||||
// (the handler ends the parse at the first value, so that the million
|
||||
// values are not read)
|
||||
ValuelessEventCounter sax;
|
||||
sax.stop_after = 1;
|
||||
CHECK(!json::sax_parse(single, &sax, json::input_format_t::ubjson));
|
||||
CHECK(sax.error_id == 0);
|
||||
CHECK(sax.values == 1);
|
||||
}
|
||||
|
||||
SECTION("to_ubjson writes the typed form up to the base only")
|
||||
{
|
||||
// 1048 rows of 1000 values fit under the base of 1048576, the 1049th
|
||||
// would not: its elements are written one by one. Written all typed,
|
||||
// 1100 rows of 6 bytes would be refused by a reader (1075 rows are the
|
||||
// most it accepts). The rows hold null, true or false, and the
|
||||
// fallback does not depend on which
|
||||
std::vector<std::uint8_t> encoded;
|
||||
{
|
||||
json table = json::array();
|
||||
for (int row = 0; row < 1100; ++row)
|
||||
{
|
||||
const json cell = row % 3 == 0 ? json(nullptr) : json(row % 3 == 1);
|
||||
table.push_back(json(1000, cell));
|
||||
}
|
||||
encoded = json::to_ubjson(table, true, true);
|
||||
}
|
||||
// outer array: `[$[#I` and the count (7 bytes), then 1048 typed rows of 6
|
||||
// bytes (`$Z#I` and two bytes) and 52 rows of `#I`, two bytes, and 1000 `Z`
|
||||
CHECK(encoded.size() == 7 + (1048 * 6) + (52 * (4 + 1000)));
|
||||
|
||||
// the output is read back
|
||||
ValuelessEventCounter sax;
|
||||
CHECK(json::sax_parse(encoded, &sax, json::input_format_t::ubjson));
|
||||
CHECK(sax.error_id == 0);
|
||||
CHECK(sax.values == 1100u * 1000u);
|
||||
}
|
||||
|
||||
SECTION("BJData is not affected")
|
||||
{
|
||||
// BJData has no optimized arrays of these types, and the writer does
|
||||
// not charge them
|
||||
json table = json::array();
|
||||
for (int row = 0; row < 3; ++row)
|
||||
{
|
||||
table.push_back(json(10, nullptr));
|
||||
}
|
||||
const auto encoded = json::to_bjdata(table, true, true);
|
||||
CHECK(json::from_bjdata(encoded) == table);
|
||||
|
||||
const std::vector<std::uint8_t> input = {'[', '$', 'Z', '#', 'l', 0x00, 0x10, 0x00, 0x00};
|
||||
CHECK_THROWS_AS(_ = json::from_bjdata(input), json::parse_error&);
|
||||
}
|
||||
|
||||
SECTION("an object of a valueless type needs a key for every value")
|
||||
{
|
||||
// an object member costs a key, so the count is bounded by the input
|
||||
// and is not charged to the budget
|
||||
const std::vector<std::uint8_t> input = {'{', '$', 'Z', '#', 'l', 0x00, 0x10, 0x00, 0x00};
|
||||
ValuelessEventCounter sax;
|
||||
CHECK(!json::sax_parse(input, &sax, json::input_format_t::ubjson));
|
||||
CHECK(sax.error_id == 110);
|
||||
CHECK(sax.values == 0);
|
||||
}
|
||||
}
|
||||
|
||||
TEST_CASE("UBJSON an optimized array of no-ops is empty whatever its count")
|
||||
{
|
||||
// A no-op ('N') is not a value, so `[$N#<n>` is an array without elements
|
||||
// for every n. The count used to be passed on to the SAX parser, which
|
||||
// told it to expect n elements, and the DOM parser reserved storage for
|
||||
// them: 16384 values (256 KB) for a count of 2^31 in 9 bytes of input.
|
||||
SECTION("the SAX parser is told that the array is empty")
|
||||
{
|
||||
for (const std::vector<std::uint8_t>& input :
|
||||
{
|
||||
std::vector<std::uint8_t> {'[', '$', 'N', '#', 'i', 2},
|
||||
std::vector<std::uint8_t> {'[', '$', 'N', '#', 'I', 0x7F, 0xFF},
|
||||
std::vector<std::uint8_t> {'[', '$', 'N', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF},
|
||||
std::vector<std::uint8_t> {'[', '$', 'N', '#', 'i', 0}
|
||||
})
|
||||
{
|
||||
SaxEventLogger logger;
|
||||
CHECK(json::sax_parse(input, &logger, json::input_format_t::ubjson));
|
||||
CHECK(logger.events == std::vector<std::string>({"start_array(0)", "end_array()"}));
|
||||
}
|
||||
|
||||
// between other values, the next value is read as usual
|
||||
const std::vector<std::uint8_t> nested = {'[', '[', '$', 'N', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF, 'T', '[', '$', 'N', '#', 'i', 3, ']'};
|
||||
SaxEventLogger logger;
|
||||
CHECK(json::sax_parse(nested, &logger, json::input_format_t::ubjson));
|
||||
CHECK(logger.events == std::vector<std::string>({"start_array()", "start_array(0)", "end_array()", "boolean(true)", "start_array(0)", "end_array()", "end_array()"}));
|
||||
}
|
||||
|
||||
SECTION("the DOM parser reserves nothing")
|
||||
{
|
||||
// 2000 arrays of 9 bytes that announce 2^31 elements each: with a
|
||||
// reservation of 16384 values per array this took about 500 MB
|
||||
std::vector<std::uint8_t> input = {'['};
|
||||
for (int i = 0; i < 2000; ++i)
|
||||
{
|
||||
input.insert(input.end(), {'[', '$', 'N', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF});
|
||||
}
|
||||
input.push_back(']');
|
||||
|
||||
const json j = json::from_ubjson(input);
|
||||
REQUIRE(j.size() == 2000);
|
||||
std::size_t capacity = 0;
|
||||
for (const auto& element : j)
|
||||
{
|
||||
CHECK(element.is_array());
|
||||
CHECK(element.empty());
|
||||
capacity += element.get_ref<const json::array_t&>().capacity();
|
||||
}
|
||||
CHECK(capacity == 0);
|
||||
|
||||
// the 7-byte form inside an optimized array of arrays
|
||||
std::vector<std::uint8_t> typed = {'[', '$', '[', '#', 'I', 0x07, 0xD0};
|
||||
for (int i = 0; i < 2000; ++i)
|
||||
{
|
||||
typed.insert(typed.end(), {'$', 'N', '#', 'I', 0x7F, 0xFF});
|
||||
}
|
||||
const json k = json::from_ubjson(typed);
|
||||
REQUIRE(k.size() == 2000);
|
||||
capacity = 0;
|
||||
for (const auto& element : k)
|
||||
{
|
||||
CHECK(element.empty());
|
||||
capacity += element.get_ref<const json::array_t&>().capacity();
|
||||
}
|
||||
CHECK(capacity == 0);
|
||||
}
|
||||
|
||||
SECTION("a count that no container could hold is no longer an error")
|
||||
{
|
||||
// the array is empty, so nothing has to fit: 0x7FFFFFFF used to be
|
||||
// reported as out_of_range.408 where it exceeds the maximum size of
|
||||
// an array, and is accepted now
|
||||
const std::vector<std::uint8_t> input = {'[', '$', 'N', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF};
|
||||
CHECK(json::from_ubjson(input) == json::array());
|
||||
|
||||
// a count that does not fit into std::size_t still is
|
||||
#if SIZE_MAX == 0xffffffff
|
||||
const std::vector<std::uint8_t> too_large = {'[', '$', 'N', '#', 'L', 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00};
|
||||
json _;
|
||||
CHECK_THROWS_AS(_ = json::from_ubjson(too_large), json::out_of_range&);
|
||||
#endif
|
||||
}
|
||||
}
|
||||
|
||||
TEST_CASE("issue #5405 - array reserve for definite-length UBJSON arrays")
|
||||
{
|
||||
#if !defined(JSON_NOEXCEPTION)
|
||||
|
||||
Reference in new issue
Block a user