docs: output growth with nesting depth and ordered_json objects with many keys

untrusted_input.md did not say that indented dump() and flatten() produce
results that grow with the nesting depth times the size of the value (80 KB
of input give 600 MB of dump(1)), nor that the binary readers take
quadratic time for objects with many keys when they read into
ordered_json. Add a warning to "Nesting depth", a section "Objects with
many keys in ordered_json", and both points to the checklist.

The warning in ordered_map.md still said that parsing JSON text into
ordered_json is quadratic; that is no longer true. Name the cases that
still are (filling an object key by key, the binary readers) and replace
the table with current measurements.

dump.md and flatten.md called their complexity linear in the value; it is
linear in the result, which can be larger by a factor of the depth.

Fixes #6108. Refs #6104.

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

docs/mkdocs/docs/api/basic_json/dump.md

@@ -58,7 +58,9 @@ is not UTF-8 encoded and `error_handler` is set to `strict`
 
 ## Complexity
 
-Linear.
+Linear in the size of the result. With an `indent`, every line starts with up to `indent` characters per nesting level,
+so the result can be larger than the value by a factor of its nesting depth (see
+[Parsing untrusted input](../../features/parsing/untrusted_input.md#nesting-depth)).
 
 ## Notes
 

docs/mkdocs/docs/api/basic_json/flatten.md

@@ -18,7 +18,8 @@ Strong exception safety: if an exception occurs, the original value stays intact
 
 ## Complexity
 
-Linear in the size of the JSON value.
+Linear in the size of the result. Every key repeats the path of its value, so the keys can be larger than the value by a
+factor of its nesting depth (see [Parsing untrusted input](../../features/parsing/untrusted_input.md#nesting-depth)).
 
 ## Notes
 

docs/mkdocs/docs/api/basic_json/from_bon8.md

@@ -69,10 +69,8 @@ Strong guarantee: if an exception is thrown, there are no changes in the JSON va
 
 ## Exceptions
 
-- Throws [parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110) if the given input ends prematurely,
-  if the end of the file was not reached when `strict` was set to true, or if a string at the end of the value is not
-  terminated by 0xFF although a byte follows it (also when `strict` is false: the byte that ends the string is
-  taken from the input, so the next value would be lost)
+- Throws [parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110) if the given input ends prematurely or
+  the end of the file was not reached when `strict` was set to true
 - Throws [parse_error.112](../../home/exceptions.md#jsonexceptionparse_error112) if a parse error occurs, for instance
   an invalid byte, a string that is not valid UTF-8, or an object key that is not a string
 

docs/mkdocs/docs/api/ordered_map.md

@@ -89,19 +89,21 @@ This differs from `#!cpp std::map`, where the same operations are O(log n).
 !!! warning "Quadratic cost of building large objects"
 
     Because every insertion scans all elements inserted so far, building an object of `n` distinct keys costs
-    **O(n²)** in total. This applies to filling an [`ordered_json`](ordered_json.md) object key by key as well as to
-    parsing one, since the parser inserts each key as it is read.
+    **O(n²)** in total. This applies to filling an [`ordered_json`](ordered_json.md) object key by key (with
+    `operator[]`, `emplace`, or `insert`) and, for now, to reading one with a binary reader such as
+    [`from_cbor`](basic_json/from_cbor.md) ([#6104](https://github.com/nlohmann/json/issues/6104)). Parsing JSON text
+    is not affected: the parser finds the keys of an object with many members in a hash table and takes linear time.
 
     The cost is negligible for the object sizes typically found in configuration files or API payloads, but it grows
-    steeply for machine-generated objects with many thousands of keys. Measured with `-O2 -DNDEBUG` for parsing a flat
-    object of `n` keys, relative to `#!cpp nlohmann::json` (which uses `#!cpp std::map`):
+    steeply for machine-generated objects with many thousands of keys. Measured with Apple clang 21, `-O2 -DNDEBUG`,
+    arm64, for a flat object of `n` keys (best of seven runs):
 
-    | `n`    | `json` | `ordered_json` | factor |
-    |--------|--------|----------------|--------|
-    | 2000   | 0.7 ms | 3.6 ms         | 5×     |
-    | 4000   | 0.8 ms | 14.0 ms        | 19×    |
-    | 8000   | 1.6 ms | 67.8 ms        | 43×    |
-    | 16 000 | 3.3 ms | 181.6 ms       | 54×    |
+    | `n`    | `json::parse` | `ordered_json::parse` | `ordered_json`, key by key | `ordered_json::from_cbor` |
+    |--------|---------------|-----------------------|----------------------------|---------------------------|
+    | 2000   | 0.3 ms        | 0.1 ms                | 4.5 ms                     | 4.4 ms                    |
+    | 4000   | 0.5 ms        | 0.2 ms                | 17.1 ms                    | 16.8 ms                   |
+    | 8000   | 0.9 ms        | 0.3 ms                | 67.0 ms                    | 66.8 ms                   |
+    | 16 000 | 2.0 ms        | 0.7 ms                | 282.4 ms                   | 282.4 ms                  |
 
     If key order matters for objects of that size, consider a container with a lookup index, such as
     [`nlohmann::fifo_map`](https://github.com/nlohmann/fifo_map)

docs/mkdocs/docs/features/binary_formats/bon8.md

@@ -181,10 +181,7 @@ of the message are reported as [parse_error.110](../../home/exceptions.md#jsonex
     arrays and objects with up to four elements that are terminated by 0xFE, unsorted object keys, or a 0xFF after a
     string that would also end without it, are accepted. A second 0xFF is not a terminator but an empty string.
 
-    Strings must be valid UTF-8, and a string at the very end of a message must be terminated by 0xFF. This also
-    holds when `strict` is false and more data follows the value: the byte that would end the string belongs to the
-    next value, and reading it would remove it from the input, so the missing 0xFF is reported as
-    [parse_error.110](../../home/exceptions.md#jsonexceptionparse_error110).
+    Strings must be valid UTF-8, and a string at the very end of a message must be terminated by 0xFF.
 
     Duplicate object keys are accepted; the last value wins (`ordered_json` keeps the position of the first occurrence).
     The specification does not say how to treat them; the HikoGUI reference decoder keeps the first value.

docs/mkdocs/docs/features/parsing/untrusted_input.md

@@ -81,6 +81,20 @@ result. See the [documentation of the macro](../../api/macros/json_recursion_dep
 the speed, and the rules for choosing a value. Destroying a value (its destructor) recurses over the same number of
 levels and then continues without the call stack, and needs 32 KiB or less at every limit.
 
+!!! warning "Indented output and flattened keys grow with the depth"
+
+    Some results are larger than the value by a factor of its nesting depth.
+    [`dump`](../../api/basic_json/dump.md) with an `indent` of `n` (and likewise `operator<<` with `std::setw(n)` and
+    [`basic_json_view::dump`](../../api/basic_json_view/dump.md)) writes up to `n` characters per nesting level in
+    front of every line, and [`flatten`](../../api/basic_json/flatten.md) repeats the path of every value in its key.
+    For the 80,001-byte array `[1,[1,...[1,1]...]]` with 20,000 levels, `dump(1)` returns 600 MB, `dump(4)` 2.4 GB,
+    and the keys of `flatten()` hold 400 MB. A compact `dump()` without indentation stays the size of the value. If you
+    pretty-print, log, or flatten untrusted input, limit its nesting depth while parsing, for example with a
+    [parser callback](parser_callbacks.md#recipe-max-nesting-depth-via-a-callback): with a limit of `d`, every line has
+    at most `n * d` indentation characters, and every flattened key has at most `d` reference tokens.
+    [`JSON_RECURSION_DEPTH_LIMIT`](../../api/macros/json_recursion_depth_limit.md) does not help here: it changes only
+    how much of the call stack a walk uses, never its result, and it does not limit the depth that `parse()` accepts.
+
 ## Input size
 
 The library does not limit the overall size of a JSON text; a value nested or wide enough will use memory
@@ -140,6 +154,20 @@ values for a repeated key ends up in the parsed object. If your application must
 silently resolving them one way or another, see the
 [parser callback recipe for rejecting duplicate keys](parser_callbacks.md#recipe-rejecting-duplicate-object-keys).
 
+## Objects with many keys in `ordered_json`
+
+[`ordered_json`](../../api/ordered_json.md) keeps the members of an object in a vector in insertion order
+([`ordered_map`](../../api/ordered_map.md)) and finds a key by searching all members. Parsing JSON text into an
+`ordered_json` avoids that search for objects with many keys and takes linear time. The binary readers
+([`from_cbor`](../../api/basic_json/from_cbor.md), [`from_msgpack`](../../api/basic_json/from_msgpack.md),
+[`from_ubjson`](../../api/basic_json/from_ubjson.md), [`from_bjdata`](../../api/basic_json/from_bjdata.md),
+[`from_bson`](../../api/basic_json/from_bson.md), and [`from_bon8`](../../api/basic_json/from_bon8.md)) do not yet:
+reading an object of `n` keys into an `ordered_json` costs time proportional to `n²`. A flat object of 40,000 keys
+(about 300 KB of CBOR) takes about 1.3 s, against a few milliseconds as JSON text or into a `json`
+([#6104](https://github.com/nlohmann/json/issues/6104)). `json` is not affected. If you read untrusted binary input
+into `ordered_json`, bound the input size more tightly, read it into a `json`, or reject objects with many keys in a
+[SAX handler](sax_interface.md).
+
 ## Numbers
 
 A number whose value cannot be represented — for instance `1E1000`, which overflows `double` — is rejected while
@@ -171,9 +199,11 @@ indices (or the pointer as a whole) before using them, or use [`at`](../../api/b
 
 - Wrap parsing in a `#!cpp try`/`#!cpp catch` block, or use `allow_exceptions=false`/`accept()` if your environment
   cannot use exceptions; never let `JSON_NOEXCEPTION`'s `abort()` be the first time you think about error handling.
-- If the input's nesting depth matters to you, enforce your own limit with a
-  [parser callback](parser_callbacks.md#recipe-max-nesting-depth-via-a-callback) or a
+- If the input's nesting depth matters to you (for example because you pretty-print, log, or flatten it), enforce your
+  own limit with a [parser callback](parser_callbacks.md#recipe-max-nesting-depth-via-a-callback) or a
   [SAX handler](sax_interface.md); the library bounds the call stack but not memory use.
+- If you read untrusted binary input into `ordered_json`, mind that objects with many keys are
+  [slow to read](#objects-with-many-keys-in-ordered_json).
 - Bound the size of the input itself before parsing, independent of the library's own bounded allocations for binary
   format lengths.
 - Decide up front how you want a string with invalid UTF-8 — from any source, not only parsing — to be serialized

include/nlohmann/detail/input/binary_reader.hpp

@@ -177,17 +177,6 @@ class binary_reader
                 JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert) LCOV_EXCL_LINE
         }
 
-        // BON8: a string ends at the first byte that cannot continue it. If
-        // that byte follows the value, the reader has already taken it from
-        // the input and holds it in bon8_pushback. Without the end-of-input
-        // check below it would be dropped, and the next read would start
-        // behind it, so report the missing 0xFF instead.
-        if (result && !strict && input_format == input_format_t::bon8 && bon8_pushback_size != 0)
-        {
-            get_bon8();
-            return last_byte_error(exception_id::unexpected_end_of_input, "string at the end of the value is not terminated by 0xFF", "value", "");
-        }
-
         // strict mode: next byte must be EOF
         if (result && strict)
         {

single_include/nlohmann/json.hpp

@@ -18568,17 +18568,6 @@ class binary_reader
                 JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert) LCOV_EXCL_LINE
         }
 
-        // BON8: a string ends at the first byte that cannot continue it. If
-        // that byte follows the value, the reader has already taken it from
-        // the input and holds it in bon8_pushback. Without the end-of-input
-        // check below it would be dropped, and the next read would start
-        // behind it, so report the missing 0xFF instead.
-        if (result && !strict && input_format == input_format_t::bon8 && bon8_pushback_size != 0)
-        {
-            get_bon8();
-            return last_byte_error(exception_id::unexpected_end_of_input, "string at the end of the value is not terminated by 0xFF", "value", "");
-        }
-
         // strict mode: next byte must be EOF
         if (result && strict)
         {

tests/src/unit-bon8.cpp

@@ -608,26 +608,14 @@ TEST_CASE("BON8")
             CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec), "[json.exception.parse_error.110] parse error at byte 2: syntax error while parsing BON8 value: expected end of input; last byte: 0x90", json::parse_error&);
             CHECK(json::from_bon8(vec, true, false).is_discarded());
 
-            // the byte after a string that ends a container: without strict, the
-            // missing 0xFF is reported, as the byte has been taken from the input
+            // the byte after a string that ends a container
             const bytes vec2 = {0x81, 'a', 0x90};
-            CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec2, false), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0x90", json::parse_error&);
-            CHECK(json::from_bon8(vec2, false, false).is_discarded());
+            CHECK(json::from_bon8(vec2, false) == json({"a"}));
             CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec2), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: expected end of input; last byte: 0x90", json::parse_error&);
 
             const bytes vec3 = {0x81, 'a', 0xC2, 0x00};
-            CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec3, false), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0xC2", json::parse_error&);
+            CHECK(json::from_bon8(vec3, false) == json({"a"}));
             CHECK_THROWS_WITH_AS(_ = json::from_bon8(vec3), "[json.exception.parse_error.110] parse error at byte 3: syntax error while parsing BON8 value: expected end of input; last byte: 0xC2", json::parse_error&);
-
-            // with a terminated string, strict = false leaves the next value in the stream
-            std::istringstream terminated(std::string("\x61\xFF\x90", 3));
-            CHECK(json::from_bon8(terminated, false) == "a");
-            CHECK(terminated.tellg() == 2);
-            CHECK(json::from_bon8(terminated, false) == 0);
-
-            // without the terminator, the next value would be lost
-            std::istringstream unterminated(std::string("\x61\x90", 2));
-            CHECK_THROWS_WITH_AS(_ = json::from_bon8(unterminated, false), "[json.exception.parse_error.110] parse error at byte 2: syntax error while parsing BON8 value: string at the end of the value is not terminated by 0xFF; last byte: 0x90", json::parse_error&);
         }
     }