fix: avoid quadratic re-scan of comments after a value (#1689)

* fix: avoid quadratic re-scan of comments after a value

OurReader::readComment() decides whether a comment should be attached to
the previous value (commentAfterOnSameLine) by scanning the input from the
end of that value up to the comment with containsNewLine(). lastValueEnd_
only advances when a new value is read, so a long run of comments after a
value (e.g. during error recovery, or a value followed by many comments)
made every comment re-scan the same growing prefix, giving O(n^2) parse
time. A jsoncpp_fuzzer testcase took ~18s for a 400KB input.

A comment can only ever be on the same line as the last value if no
newline separates them, and the gap to inspect only grows as further
comments are consumed, so once the gap has been examined for the first
comment it never needs to be examined again. Mark lastValueHasAComment_
after the first comment following a value so subsequent comments skip the
scan. Parsing the testcase drops from ~18s to ~56ms with identical output.

Add a regression test that parses a value followed by a large number of
trailing comments and requires it to complete well under a generous time
bound.

* test: assert linear comment scanning deterministically

Replace the wall-clock bound in the comment regression test with a
direct, deterministic assertion on work done. The parse output is
identical with and without the fix, so the only observable difference is
how much the parser scans; a time bound is also flaky under
valgrind/sanitizers/loaded CI.

Add an instrumentation counter for the bytes examined by
OurReader::containsNewLine, exposed via a JSON_API seam, and assert it
stays linear in the input (scanned < 4 * doc.size()) rather than
O(comments * gap). The counter is thread_local (no race during
concurrent parsing) and the increment is negligible, running only while
parsing comments. It is compiled unconditionally because the ABI
compatibility job builds the test suite against a separately-installed
Release library, so the symbol must exist there. Rename the test to
parseCommentsAfterValueScansLinearly to describe what it checks, and
link crbug.com/521541633.

Verified: the test fails when the fix is reverted and passes with it, in
Debug and Release, and the seam links against a Release-installed shared
library (the ABI compatibility scenario).

---------

Co-authored-by: Jordan Bayles <jophba@chromium.org>

src/lib_json/json_reader.cpp

diff --git a/src/lib_json/json_reader.cpp b/src/lib_json/json_reader.cpp
index 83743f7..39ebcc6 100644
--- a/src/lib_json/json_reader.cpp
+++ b/src/lib_json/json_reader.cpp
@@ -975,8 +975,20 @@
 
 // complete copy of Read impl, for OurReader
 
+// Test-only instrumentation: total bytes examined by
+// OurReader::containsNewLine, so unit tests can assert that comment handling
+// stays linear in the input rather than quadratic in the comment count (see
+// CharReaderTest/parseCommentsAfterValueScansLinearly). thread_local so it
+// never races during concurrent parsing; the increment is negligible and only
+// runs while parsing comments. Not part of the supported public API.
+JSON_API size_t& newlineScanByteCountForTesting() {
+  static thread_local size_t count = 0;
+  return count;
+}
+
 bool OurReader::containsNewLine(OurReader::Location begin,
                                 OurReader::Location end) {
+  newlineScanByteCountForTesting() += static_cast<size_t>(end - begin);
   return std::any_of(begin, end, [](char b) { return b == '\n' || b == '\r'; });
 }
 
@@ -1296,9 +1308,13 @@
       if (lastValueEnd_ && !containsNewLine(lastValueEnd_, commentBegin)) {
         if (isCppStyleComment || !cStyleWithEmbeddedNewline) {
           placement = commentAfterOnSameLine;
-          lastValueHasAComment_ = true;
         }
       }
+      // The gap between the last value and this comment only grows as more
+      // comments are consumed, so a later comment can never be on the same
+      // line as that value. Mark it handled to avoid re-scanning the same
+      // growing prefix for every following comment (quadratic behavior).
+      lastValueHasAComment_ = true;
     }
 
     addComment(commentBegin, current_, placement);

src/test_lib_json/main.cpp

diff --git a/src/test_lib_json/main.cpp b/src/test_lib_json/main.cpp
index 08731f6..9d13fdb 100644
--- a/src/test_lib_json/main.cpp
+++ b/src/test_lib_json/main.cpp
@@ -29,6 +29,11 @@
 
 using CharReaderPtr = std::unique_ptr<Json::CharReader>;
 
+namespace Json {
+// Defined in json_reader.cpp; test instrumentation seam.
+JSON_API size_t& newlineScanByteCountForTesting();
+} // namespace Json
+
 // Make numeric limits more convenient to talk about.
 // Assumes int type in 32 bits.
 #define kint32max Json::Value::maxInt
@@ -3308,6 +3313,42 @@
   }
 }
 
+JSONTEST_FIXTURE_LOCAL(CharReaderTest, parseCommentsAfterValueScansLinearly) {
+  // A value, then a comment whose only newline is at its end, then many
+  // trailing comments. Comment handling should scan the value->comment gap a
+  // bounded number of times (linear in the input), not once per trailing
+  // comment (O(comments * gap)). Assert directly on bytes scanned
+  // (deterministic) rather than wall-clock time (flaky under valgrind/CI).
+  //
+  // Regression test for crbug.com/521541633 (jsoncpp_fuzzer timeout: a 400KB
+  // input scanned 2.24GB across 8384 containsNewLine calls, ~18s).
+  const int kFiller = 256;
+  const int kComments = 1000;
+  std::string doc = "[0 /*";
+  doc.append(kFiller, 'a');
+  doc += "\n*/";
+  for (int i = 0; i < kComments; ++i)
+    doc += "/*c*/";
+  doc += "]";
+
+  Json::CharReaderBuilder b;
+  CharReaderPtr reader(b.newCharReader());
+  Json::Value root;
+  Json::String errs;
+
+  Json::newlineScanByteCountForTesting() = 0;
+  const bool ok =
+      reader->parse(doc.data(), doc.data() + doc.size(), &root, &errs);
+
+  JSONTEST_ASSERT(ok);
+  JSONTEST_ASSERT(errs.empty());
+  JSONTEST_ASSERT_EQUAL(0, root[0]);
+  // Quadratic-regression guard. Linear scans ~O(input); the bug scanned
+  // ~kComments * kFiller (~2.7M here vs a few bytes fixed).
+  const size_t scanned = Json::newlineScanByteCountForTesting();
+  JSONTEST_ASSERT(scanned < 4 * doc.size());
+}
+
 JSONTEST_FIXTURE_LOCAL(CharReaderTest, parseObjectWithErrors) {
   Json::CharReaderBuilder b;
   CharReaderPtr reader(b.newCharReader());