mirror of
https://github.com/nlohmann/json.git
synced 2026-11-13 15:35:23 +00:00
Compare commits
1
Commits
| Author | SHA1 | Date | |
|---|---|---|---|
 Niels Lohmann
|
964b433dc7 |
No files matched your search
@@ -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 2.3 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 1.8 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 576 KiB of stack in an unoptimized build already, twice as much as the
|
||||
useful: `254` levels need up to 448 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<<` | 48 / 32 | 80 / 64 | 144 / 128 | 288 / 256 | 576 / 512 |
|
||||
| `dump()` and `dump(indent)`, `operator<<` | 16 / 16 | 16 / 16 | 32 / 32 | 48 / 48 | 96 / 96 |
|
||||
| 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,23 +123,24 @@ The rule of thumb is
|
||||
|
||||
> stack needed ≈ a few KiB + cost per level × limit
|
||||
|
||||
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.
|
||||
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.
|
||||
|
||||
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 | 0 |
|
||||
| 64 KiB | 128 | 16 |
|
||||
| 128 KiB (the default stack of threads on musl) | 254 | 32 |
|
||||
| 256 KiB | 254 | 64 |
|
||||
| 512 KiB | 254 | 128 |
|
||||
| 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 |
|
||||
| 1 MiB or more | 254 | 254 |
|
||||
|
||||
### Speed
|
||||
|
||||
@@ -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 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`:
|
||||
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`:
|
||||
|
||||
| Stack needed, in KiB | limit 0 | limit 32 | limit 128 (default) | limit 254 |
|
||||
|---|---:|---:|---:|---:|
|
||||
| unoptimized build (`-O0`) | 16 or less | 80 | 288 | 576 |
|
||||
| unoptimized build (`-O0`) | 16 or less | 64 | 224 | 448 |
|
||||
| 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
|
||||
|
||||
@@ -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;
|
||||
}
|
||||
|
||||
|
||||
@@ -230,6 +230,16 @@
|
||||
// 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,6 +11,7 @@
|
||||
// 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
|
||||
|
||||
@@ -265,7 +265,7 @@ class serializer
|
||||
for a container; writing them from here spares each the entry and exit of
|
||||
that function.
|
||||
*/
|
||||
JSON_HEDLEY_ALWAYS_INLINE void dump_element(const BasicJsonType& val,
|
||||
JSON_INTERNAL_SERIALIZER_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_HEDLEY_ALWAYS_INLINE void emit_pending(std::size_t& bytes)
|
||||
JSON_INTERNAL_SERIALIZER_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_HEDLEY_ALWAYS_INLINE void reserve_string_buffer(std::size_t& bytes)
|
||||
JSON_INTERNAL_SERIALIZER_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_HEDLEY_ALWAYS_INLINE void put_indent(std::size_t indent)
|
||||
JSON_INTERNAL_SERIALIZER_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_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)
|
||||
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)
|
||||
{
|
||||
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_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)
|
||||
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)
|
||||
{
|
||||
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_HEDLEY_ALWAYS_INLINE void put_literal(const char (&s)[N]) // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
|
||||
JSON_INTERNAL_SERIALIZER_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
|
||||
|
||||
Generated
+153
-372
@@ -2603,6 +2603,16 @@ JSON_HEDLEY_DIAGNOSTIC_POP
|
||||
// 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
|
||||
@@ -27139,6 +27149,139 @@ class json_pointer
|
||||
}
|
||||
|
||||
private:
|
||||
/*!
|
||||
@brief the pointer prefixes of a flattened object that denote arrays
|
||||
|
||||
@ref unflatten creates arrays exactly below the prefixes that have a
|
||||
reference token 0 among their children, and objects everywhere else.
|
||||
Deciding this up front keeps the result independent of the order in which
|
||||
the flattened object is iterated, which is unspecified for some object
|
||||
types.
|
||||
|
||||
A prefix is identified by the text of the key it is the beginning of:
|
||||
escaping is unambiguous, so equal prefixes of valid keys are equal texts.
|
||||
The set refers to the keys, which must outlive it.
|
||||
*/
|
||||
class array_prefix_set
|
||||
{
|
||||
public:
|
||||
void insert(const char* data, std::size_t size)
|
||||
{
|
||||
// flattened objects are usually sorted, so most keys that have a
|
||||
// 0 yield the prefix of the previous one
|
||||
if (last_data != nullptr && last_size == size && std::memcmp(last_data, data, size) == 0)
|
||||
{
|
||||
return;
|
||||
}
|
||||
last_data = data;
|
||||
last_size = size;
|
||||
|
||||
if (table.empty())
|
||||
{
|
||||
table.resize(16);
|
||||
}
|
||||
const std::size_t hash = hash_of(data, size);
|
||||
const std::size_t mask = table.size() - 1;
|
||||
std::size_t i = hash & mask;
|
||||
while (table[i].data != nullptr)
|
||||
{
|
||||
if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
|
||||
{
|
||||
return;
|
||||
}
|
||||
i = (i + 1) & mask;
|
||||
}
|
||||
table[i] = slot(hash, data, size);
|
||||
|
||||
// keep the load factor below 1/2
|
||||
if (++used * 2 > table.size())
|
||||
{
|
||||
grow();
|
||||
}
|
||||
}
|
||||
|
||||
bool empty() const noexcept
|
||||
{
|
||||
return used == 0;
|
||||
}
|
||||
|
||||
bool contains(const char* data, std::size_t size) const noexcept
|
||||
{
|
||||
if (used == 0)
|
||||
{
|
||||
return false;
|
||||
}
|
||||
const std::size_t hash = hash_of(data, size);
|
||||
const std::size_t mask = table.size() - 1;
|
||||
for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
|
||||
{
|
||||
if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
|
||||
{
|
||||
return true;
|
||||
}
|
||||
}
|
||||
return false;
|
||||
}
|
||||
|
||||
private:
|
||||
struct slot
|
||||
{
|
||||
slot() noexcept = default;
|
||||
|
||||
slot(std::size_t h, const char* d, std::size_t s) noexcept
|
||||
: hash(h), data(d), size(s)
|
||||
{}
|
||||
|
||||
std::size_t hash = 0;
|
||||
const char* data = nullptr; // nullptr: the slot is empty
|
||||
std::size_t size = 0;
|
||||
};
|
||||
|
||||
static std::size_t hash_of(const char* data, std::size_t size) noexcept
|
||||
{
|
||||
std::uint64_t h = 0x9E3779B97F4A7C15ULL ^ size;
|
||||
std::size_t i = 0;
|
||||
for (; i + 8 <= size; i += 8)
|
||||
{
|
||||
std::uint64_t w = 0;
|
||||
std::memcpy(&w, data + i, 8);
|
||||
h = (h ^ w) * 0x100000001B3ULL;
|
||||
h ^= h >> 32u;
|
||||
}
|
||||
std::uint64_t w = 0;
|
||||
if (i < size)
|
||||
{
|
||||
std::memcpy(&w, data + i, size - i);
|
||||
}
|
||||
h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
|
||||
return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
|
||||
}
|
||||
|
||||
void grow()
|
||||
{
|
||||
std::vector<slot> old(table.size() * 2);
|
||||
old.swap(table);
|
||||
const std::size_t mask = table.size() - 1;
|
||||
for (const auto& s : old)
|
||||
{
|
||||
if (s.data != nullptr)
|
||||
{
|
||||
std::size_t i = s.hash & mask;
|
||||
while (table[i].data != nullptr)
|
||||
{
|
||||
i = (i + 1) & mask;
|
||||
}
|
||||
table[i] = s;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
std::vector<slot> table{};
|
||||
std::size_t used = 0;
|
||||
const char* last_data = nullptr;
|
||||
std::size_t last_size = 0;
|
||||
};
|
||||
|
||||
/// @brief the length of the longest common prefix of the first @a limit bytes of @a a and @a b
|
||||
static std::size_t common_prefix_length(const char* a, const char* b, const std::size_t limit) noexcept
|
||||
{
|
||||
@@ -27161,355 +27304,6 @@ class json_pointer
|
||||
return i;
|
||||
}
|
||||
|
||||
/*!
|
||||
@brief the prefixes of a flattened object that are marked as arrays, for
|
||||
prefixes that are not short
|
||||
|
||||
A prefix is identified by the tokens it consists of: a node of a tree
|
||||
stands for the prefix of its parent followed by a token, and is looked up
|
||||
by its parent and the text of the token. The node of a prefix is found by
|
||||
walking the tokens of the key from the root, so identifying all prefixes
|
||||
of a key together costs one pass over the key, however long the prefixes
|
||||
are, and no prefix is ever compared byte by byte as a whole. The nodes
|
||||
along the key that was walked last are kept, and the walk of the next key
|
||||
starts below the beginning it has in common with that key. The tree refers
|
||||
to the keys, which must outlive it.
|
||||
*/
|
||||
class prefix_tree
|
||||
{
|
||||
public:
|
||||
/// @brief set the seed of the hash function, before anything is added
|
||||
void reseed(const std::uint64_t seed_value) noexcept
|
||||
{
|
||||
seed = seed_value;
|
||||
}
|
||||
|
||||
/// @brief mark the first @a prefix_size bytes of the key of @a key_size bytes at @a data
|
||||
void mark(const char* data, std::size_t key_size, std::size_t prefix_size)
|
||||
{
|
||||
nodes[walk(data, key_size, prefix_size)].marked = true;
|
||||
any_marked = true;
|
||||
}
|
||||
|
||||
bool is_marked(const char* data, std::size_t key_size, std::size_t prefix_size)
|
||||
{
|
||||
return any_marked && nodes[walk(data, key_size, prefix_size)].marked;
|
||||
}
|
||||
|
||||
bool empty() const noexcept
|
||||
{
|
||||
return !any_marked;
|
||||
}
|
||||
|
||||
/// @brief the hash of the first @a size bytes at @a data, for the seed @a seed_value
|
||||
static std::size_t hash_bytes(const char* data, std::size_t size, const std::uint64_t seed_value) noexcept
|
||||
{
|
||||
std::uint64_t h = seed_value ^ size;
|
||||
std::size_t i = 0;
|
||||
for (; i + 8 <= size; i += 8)
|
||||
{
|
||||
std::uint64_t w = 0;
|
||||
std::memcpy(&w, data + i, 8);
|
||||
h = (h ^ w) * 0x100000001B3ULL;
|
||||
h ^= h >> 32u;
|
||||
}
|
||||
std::uint64_t w = 0;
|
||||
if (i < size)
|
||||
{
|
||||
std::memcpy(&w, data + i, size - i);
|
||||
}
|
||||
h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
|
||||
return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
|
||||
}
|
||||
|
||||
private:
|
||||
struct node
|
||||
{
|
||||
std::size_t parent = 0;
|
||||
std::size_t hash = 0;
|
||||
const char* token = nullptr;
|
||||
std::size_t token_size = 0;
|
||||
bool marked = false;
|
||||
};
|
||||
|
||||
/// @brief a slot of the hash table; the index of a node, 0 if the slot is empty
|
||||
struct bucket
|
||||
{
|
||||
std::size_t index = 0;
|
||||
};
|
||||
|
||||
/// @brief the node after a token of the key that was walked last, and where the token ends
|
||||
struct step
|
||||
{
|
||||
std::size_t node = 0;
|
||||
std::size_t end = 0;
|
||||
};
|
||||
|
||||
/// @brief the index of the node of the prefix that ends at the slash (or the end) at @a prefix_size
|
||||
std::size_t walk(const char* data, std::size_t key_size, std::size_t prefix_size)
|
||||
{
|
||||
if (nodes.empty())
|
||||
{
|
||||
nodes.emplace_back();
|
||||
table.resize(16);
|
||||
chain.emplace_back();
|
||||
}
|
||||
|
||||
if (data != last_key)
|
||||
{
|
||||
// keep the nodes within the beginning that this key has in common
|
||||
// with the key they were found for; a prefix that ends inside a
|
||||
// token of this key is not one of its prefixes
|
||||
const std::size_t same = common_prefix_length(data, last_key, (std::min)(key_size, last_key_size));
|
||||
std::size_t keep = chain.size();
|
||||
while (keep > 1 && (chain[keep - 1].end > same || (chain[keep - 1].end == same && same < key_size && data[same] != '/')))
|
||||
{
|
||||
--keep;
|
||||
}
|
||||
chain.resize(keep);
|
||||
last_key = data;
|
||||
last_key_size = key_size;
|
||||
}
|
||||
|
||||
// walk the tokens that are not walked yet
|
||||
while (chain.back().end < prefix_size && chain.back().end < key_size)
|
||||
{
|
||||
const std::size_t start = chain.back().end + 1;
|
||||
const void* const slash = std::memchr(data + start, '/', key_size - start);
|
||||
const std::size_t end = slash == nullptr ? key_size : static_cast<std::size_t>(static_cast<const char*>(slash) - data);
|
||||
step next;
|
||||
next.node = child(chain.back().node, data + start, end - start);
|
||||
next.end = end;
|
||||
chain.push_back(next);
|
||||
}
|
||||
|
||||
if (chain.back().end == prefix_size)
|
||||
{
|
||||
return chain.back().node;
|
||||
}
|
||||
// an earlier call walked further
|
||||
const auto it = std::lower_bound(chain.begin(), chain.end(), prefix_size, [](const step & s, std::size_t size)
|
||||
{
|
||||
return s.end < size;
|
||||
});
|
||||
return it->node;
|
||||
}
|
||||
|
||||
std::size_t slot_of(std::size_t parent, std::size_t hash) const noexcept
|
||||
{
|
||||
std::uint64_t x = static_cast<std::uint64_t>(hash) ^ (static_cast<std::uint64_t>(parent) * 0x9E3779B97F4A7C15ULL);
|
||||
x ^= x >> 32u;
|
||||
x *= 0xD6E8FEB86659FD93ULL;
|
||||
x ^= x >> 32u;
|
||||
return static_cast<std::size_t>(x) & (table.size() - 1);
|
||||
}
|
||||
|
||||
/// @brief the node of the prefix of the node @a parent followed by the token, which is added if it is not there
|
||||
std::size_t child(std::size_t parent, const char* token, std::size_t token_size)
|
||||
{
|
||||
const std::size_t hash = hash_bytes(token, token_size, seed);
|
||||
std::size_t i = slot_of(parent, hash);
|
||||
while (table[i].index != 0)
|
||||
{
|
||||
const node& n = nodes[table[i].index];
|
||||
if (n.parent == parent && n.hash == hash && n.token_size == token_size && std::memcmp(n.token, token, token_size) == 0)
|
||||
{
|
||||
return table[i].index;
|
||||
}
|
||||
i = (i + 1) & (table.size() - 1);
|
||||
}
|
||||
|
||||
node created;
|
||||
created.parent = parent;
|
||||
created.hash = hash;
|
||||
created.token = token;
|
||||
created.token_size = token_size;
|
||||
nodes.push_back(created);
|
||||
table[i].index = nodes.size() - 1;
|
||||
|
||||
// keep the load factor below 1/2
|
||||
if (nodes.size() * 2 > table.size())
|
||||
{
|
||||
std::vector<bucket> old(table.size() * 2);
|
||||
old.swap(table);
|
||||
for (std::size_t k = 1; k < nodes.size(); ++k)
|
||||
{
|
||||
std::size_t j = slot_of(nodes[k].parent, nodes[k].hash);
|
||||
while (table[j].index != 0)
|
||||
{
|
||||
j = (j + 1) & (table.size() - 1);
|
||||
}
|
||||
table[j].index = k;
|
||||
}
|
||||
}
|
||||
return nodes.size() - 1;
|
||||
}
|
||||
|
||||
std::uint64_t seed = 0;
|
||||
/// @brief the nodes; the first is the root, the empty prefix
|
||||
std::vector<node> nodes{};
|
||||
/// @brief the nodes (not the root) in a hash table
|
||||
std::vector<bucket> table{};
|
||||
/// @brief the root, and the node after each token of the key that was walked last
|
||||
std::vector<step> chain{};
|
||||
const char* last_key = nullptr;
|
||||
std::size_t last_key_size = 0;
|
||||
bool any_marked = false;
|
||||
};
|
||||
|
||||
/*!
|
||||
@brief the pointer prefixes of a flattened object that denote arrays
|
||||
|
||||
@ref unflatten creates arrays exactly below the prefixes that have a
|
||||
reference token 0 among their children, and objects everywhere else.
|
||||
Deciding this up front keeps the result independent of the order in which
|
||||
the flattened object is iterated, which is unspecified for some object
|
||||
types.
|
||||
|
||||
A prefix is identified by the text of the key it is the beginning of:
|
||||
escaping is unambiguous, so equal prefixes of valid keys are equal texts.
|
||||
The set refers to the keys, which must outlive it. Short prefixes are
|
||||
kept in a hash table and compared as texts, which costs at most the length
|
||||
of the bound. Longer prefixes are kept in a @ref prefix_tree, because
|
||||
hashing and comparing every one of the prefixes of a key with many tokens
|
||||
from its beginning would take quadratic time.
|
||||
|
||||
The hash function depends on a seed that is derived from the address of a
|
||||
local variable, which address space layout randomization changes between
|
||||
processes, so keys cannot be crafted to collide in advance; the result
|
||||
does not depend on the seed. Where the addresses are not randomized, or
|
||||
when the seed is known, keys can collide: k short prefixes then cost
|
||||
k^2 / 2 comparisons of fewer than 64 bytes each. The long prefixes are not
|
||||
hashed as a whole.
|
||||
*/
|
||||
class array_prefix_set
|
||||
{
|
||||
public:
|
||||
/// @brief choose the seed of the hash function, before anything is added: it is derived from the address that is passed
|
||||
void reseed(const void* address) noexcept
|
||||
{
|
||||
// NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast,hicpp-use-auto,modernize-use-auto): the address is only a source of entropy
|
||||
std::uint64_t x = reinterpret_cast<std::uintptr_t>(address);
|
||||
x ^= 0x9E3779B97F4A7C15ULL;
|
||||
x *= 0xBF58476D1CE4E5B9ULL;
|
||||
seed = x ^ (x >> 31u);
|
||||
tree.reseed(seed);
|
||||
}
|
||||
|
||||
/// @brief add the first @a prefix_size bytes of the key of @a key_size bytes at @a data
|
||||
void insert(const char* data, std::size_t key_size, std::size_t prefix_size)
|
||||
{
|
||||
if (prefix_size >= short_limit)
|
||||
{
|
||||
tree.mark(data, key_size, prefix_size);
|
||||
return;
|
||||
}
|
||||
|
||||
// flattened objects are usually sorted, so most keys that have a
|
||||
// 0 yield the prefix of the previous one
|
||||
if (last_data != nullptr && last_size == prefix_size && std::memcmp(last_data, data, prefix_size) == 0)
|
||||
{
|
||||
return;
|
||||
}
|
||||
last_data = data;
|
||||
last_size = prefix_size;
|
||||
|
||||
const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
|
||||
if (table.empty())
|
||||
{
|
||||
table.resize(16);
|
||||
}
|
||||
const std::size_t mask = table.size() - 1;
|
||||
std::size_t i = hash & mask;
|
||||
while (table[i].data != nullptr)
|
||||
{
|
||||
if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
|
||||
{
|
||||
return;
|
||||
}
|
||||
i = (i + 1) & mask;
|
||||
}
|
||||
table[i] = slot(hash, data, prefix_size);
|
||||
|
||||
// keep the load factor below 1/2
|
||||
if (++used * 2 > table.size())
|
||||
{
|
||||
grow();
|
||||
}
|
||||
}
|
||||
|
||||
bool empty() const noexcept
|
||||
{
|
||||
return used == 0 && tree.empty();
|
||||
}
|
||||
|
||||
/// @brief whether the first @a prefix_size bytes of the key of @a key_size bytes at @a data were added
|
||||
bool contains(const char* data, std::size_t key_size, std::size_t prefix_size)
|
||||
{
|
||||
if (prefix_size >= short_limit)
|
||||
{
|
||||
return tree.is_marked(data, key_size, prefix_size);
|
||||
}
|
||||
if (used == 0)
|
||||
{
|
||||
return false;
|
||||
}
|
||||
const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
|
||||
const std::size_t mask = table.size() - 1;
|
||||
for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
|
||||
{
|
||||
if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
|
||||
{
|
||||
return true;
|
||||
}
|
||||
}
|
||||
return false;
|
||||
}
|
||||
|
||||
private:
|
||||
/// @brief prefixes of fewer bytes are kept in the hash table
|
||||
static constexpr std::size_t short_limit = 64;
|
||||
|
||||
struct slot
|
||||
{
|
||||
slot() noexcept = default;
|
||||
|
||||
slot(std::size_t h, const char* d, std::size_t s) noexcept
|
||||
: hash(h), data(d), size(s)
|
||||
{}
|
||||
|
||||
std::size_t hash = 0;
|
||||
const char* data = nullptr; // nullptr: the slot is empty
|
||||
std::size_t size = 0;
|
||||
};
|
||||
|
||||
void grow()
|
||||
{
|
||||
std::vector<slot> old(table.size() * 2);
|
||||
old.swap(table);
|
||||
const std::size_t mask = table.size() - 1;
|
||||
for (const auto& s : old)
|
||||
{
|
||||
if (s.data != nullptr)
|
||||
{
|
||||
std::size_t i = s.hash & mask;
|
||||
while (table[i].data != nullptr)
|
||||
{
|
||||
i = (i + 1) & mask;
|
||||
}
|
||||
table[i] = s;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
std::uint64_t seed = 0;
|
||||
prefix_tree tree{};
|
||||
std::vector<slot> table{};
|
||||
std::size_t used = 0;
|
||||
const char* last_data = nullptr;
|
||||
std::size_t last_size = 0;
|
||||
};
|
||||
|
||||
/*!
|
||||
@brief check that @a key is a valid JSON pointer, and add the prefixes of
|
||||
it that denote arrays to @a arrays
|
||||
@@ -27555,7 +27349,7 @@ class json_pointer
|
||||
// a token 0 makes the pointer before it an array
|
||||
if (i - begin == 1 && data[begin] == '0')
|
||||
{
|
||||
arrays.insert(data, size, begin - 1);
|
||||
arrays.insert(data, begin - 1);
|
||||
}
|
||||
begin = i + 1;
|
||||
}
|
||||
@@ -28598,7 +28392,6 @@ class json_pointer
|
||||
// token 0 among their children; the values below them are arrays,
|
||||
// all others are objects (see array_prefix_set)
|
||||
array_prefix_set arrays;
|
||||
arrays.reseed(&arrays);
|
||||
const string_t* previous_key = nullptr;
|
||||
for (const auto& element : *value.m_data.m_value.object)
|
||||
{
|
||||
@@ -28690,7 +28483,7 @@ class json_pointer
|
||||
case detail::value_t::null:
|
||||
{
|
||||
// a first child 0 makes the value an array without a look-up
|
||||
if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, key.size(), pos))
|
||||
if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, pos))
|
||||
{
|
||||
// some reference token below this position is 0, so the
|
||||
// value is an array
|
||||
@@ -28742,19 +28535,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;
|
||||
}
|
||||
|
||||
@@ -37215,7 +36995,7 @@ class serializer
|
||||
for a container; writing them from here spares each the entry and exit of
|
||||
that function.
|
||||
*/
|
||||
JSON_HEDLEY_ALWAYS_INLINE void dump_element(const BasicJsonType& val,
|
||||
JSON_INTERNAL_SERIALIZER_INLINE void dump_element(const BasicJsonType& val,
|
||||
const std::size_t current_indent,
|
||||
const std::size_t depth)
|
||||
{
|
||||
@@ -37921,7 +37701,7 @@ class serializer
|
||||
}
|
||||
|
||||
/// write out the bytes pending in @ref string_buffer and reset @a bytes
|
||||
JSON_HEDLEY_ALWAYS_INLINE void emit_pending(std::size_t& bytes)
|
||||
JSON_INTERNAL_SERIALIZER_INLINE void emit_pending(std::size_t& bytes)
|
||||
{
|
||||
if (bytes != 0)
|
||||
{
|
||||
@@ -37933,7 +37713,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_HEDLEY_ALWAYS_INLINE void reserve_string_buffer(std::size_t& bytes)
|
||||
JSON_INTERNAL_SERIALIZER_INLINE void reserve_string_buffer(std::size_t& bytes)
|
||||
{
|
||||
if (string_buffer.size() - bytes < 13)
|
||||
{
|
||||
@@ -38294,7 +38074,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_HEDLEY_ALWAYS_INLINE void put_indent(std::size_t indent)
|
||||
JSON_INTERNAL_SERIALIZER_INLINE void put_indent(std::size_t indent)
|
||||
{
|
||||
// closing braces at the outermost level ask for no indentation at all
|
||||
if (indent == 0)
|
||||
@@ -38348,7 +38128,7 @@ class serializer
|
||||
its room and four stores of the indentation, see @ref put_short_literal_indent.
|
||||
*/
|
||||
template<std::size_t N>
|
||||
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)
|
||||
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)
|
||||
{
|
||||
if (JSON_HEDLEY_LIKELY(put_short_literal_indent(s, indent)))
|
||||
{
|
||||
@@ -38368,7 +38148,7 @@ class serializer
|
||||
@a indent is wider or the write buffer lacks the room.
|
||||
*/
|
||||
template<std::size_t N>
|
||||
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)
|
||||
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)
|
||||
{
|
||||
constexpr std::size_t length = N - 1;
|
||||
if (indent > 32 || write_buffer_pos + length + 32 > write_buffer.size())
|
||||
@@ -38395,7 +38175,7 @@ class serializer
|
||||
write-through path for oversized runs.
|
||||
*/
|
||||
template<std::size_t N>
|
||||
JSON_HEDLEY_ALWAYS_INLINE void put_literal(const char (&s)[N]) // NOLINT(cppcoreguidelines-avoid-c-arrays,hicpp-avoid-c-arrays,modernize-avoid-c-arrays)
|
||||
JSON_INTERNAL_SERIALIZER_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
|
||||
@@ -48115,6 +47895,7 @@ struct formatter<nlohmann::NLOHMANN_BASIC_JSON_TPL, char> // NOLINT(cert-dcl58-c
|
||||
// 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
|
||||
|
||||
@@ -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());
|
||||
}
|
||||
}
|
||||
Reference in new issue
Block a user