open-source-parsers / jsoncpp
90%
master: 90%

LAST BUILD BRANCH: refs/pull/1691/merge
DEFAULT BRANCH: master
Repo Added
Files 8
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst

LAST BUILD ON BRANCH refs/tags/1.9.8-rc1
branch: refs/tags/1.9.8-rc1
CHANGE BRANCH
x

coverage: 89.949% (+0.005%) from 89.944%
27487810875

push

github

web-flow 
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... (continued)

2201 of 2614 branches covered (84.2%)

Branch coverage included in aggregate %.

4 of 4 new or added lines in 1 file covered. (100.0%)

2605 of 2729 relevant lines covered (95.46%)

23441.29 hits per line

Relevant lines Covered
2729 RELEVANT LINES 2605 COVERED LINES
23441.29 HITS PER LINE
Source Files on refs/tags/1.9.8-rc1

Recent builds

Builds Branch Commit Type Ran Committer Via Coverage
27487810875 refs/tags/1.9.8-rc1 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 scann... push web-flow github
89.95
See All Builds (766)