diff options
| author | Martin Hořeňovský | 2026-07-26 13:15:10 +0200 |
|---|---|---|
| committer | Martin Hořeňovský | 2026-07-26 19:51:58 +0200 |
| commit | 1079da4c5f5fea2a31d795bba95eacaa2f622849 (patch) | |
| tree | 4f708b68ab9038d75a50e15467b3ea8182e939f1 /extras | |
| parent | 60c8b878292ec4afc625a807cdc3902397a408a3 (diff) | |
| download | catch3-1079da4c5f5fea2a31d795bba95eacaa2f622849.tar.gz | |
Avoid quadratic JSON array parse behaviour in `catch_discover_tests`
Using CMake's `string(JSON` to parse JSON array leads to quadratic
running time in number of tests, see https://gitlab.kitware.com/cmake/cmake/-/work_items/27985
This leads to _terrible_ runtime for `catch_discover_tests` when called
on binaries with lot of tests (1k+). To get reasonable runtimes, we have
to avoid using `string(JSON` to parse out the individual test objects
from the array with all tests.
This commit replaces the sane approach of using real JSON parser with
a set of terrible hacks, where we use CMake's string APIs to split the
JSON array on what looks like object boundary (`}<ws>*,<ws>*{`), and then
checking whether the resulting thing can be parsed as JSON object. If not,
we append the next piece and check again. And again, and again, until we
get a proper JSON object.
This is all around a hilariously terrible idea, however:
1) It works in practice for all tested inputs.
2) It improves the time it takes to run `catch_discover_tests` on binary
with 1k tests from 4.2s to 1.1s and 2k tests from 16s to 3.9s.
Diffstat (limited to 'extras')
| -rw-r--r-- | extras/CatchAddTests.cmake | 154 |
1 files changed, 139 insertions, 15 deletions
diff --git a/extras/CatchAddTests.cmake b/extras/CatchAddTests.cmake index a8a20754..59a39c70 100644 --- a/extras/CatchAddTests.cmake +++ b/extras/CatchAddTests.cmake @@ -1,6 +1,131 @@ # Distributed under the OSI-approved BSD 3-Clause License. See accompanying # file Copyright.txt or https://cmake.org/licensing for details. +# Because natively using CMake's JSON processing for arrays leads to quadratic +# running times, we do terrible hack and split JSON array by object boundary +# + commas and try to reconstruct valid JSON objects. During this, we need +# to replace CMake characters that could be in the test name/tags with +# placeholder, so it doesn't affect CMake's processing of the strings/lists +# we create during the parsing. +# +# We use 0x01, 0x02, 0x03, and 0x04 as placeholder bytes, as those cannot +# exist in JSON unescaped. +# +# 0x01 <=> ';' (CMake list separator) +# 0x02 == element boundary marker used while splitting the tests array +# 0x03 <-> '[' (opens a CMake bracket-argument context) +# 0x04 <-> ']' (closes a CMake bracket-argument context) +# +string(ASCII 1 _SemicolonEscape) +string(ASCII 2 _BoundaryEscape) +string(ASCII 3 _OpenBracketEscape) +string(ASCII 4 _CloseBracketEscape) + + +# Placeholder bytes in the listing would break our parsing hack, so +# we check they don't exist. They shouldn't exist in valid JSON, but +# the reporter might not be escaping them properly. +function(validate_input_noescapes listing_var) + foreach(byte "${_SemicolonEscape}" "${_BoundaryEscape}" "${_OpenBracketEscape}" "${_CloseBracketEscape}") + string(FIND "${${listing_var}}" "${byte}" found) + if(NOT found EQUAL -1) + message(FATAL_ERROR + "The test listing contains raw control byte (0x01-0x04) which should not " + "be there. This means either bad escaping in JSON reporter, or corrupted file. " + ) + endif() + endforeach() +endfunction() + + +# Replaces relevant characters with their placeholders, see the top of this file. +# Modifies argument `var` in place. +function(magic_escape_chars var) + set(value "${${var}}") + string(REPLACE ";" "${_SemicolonEscape}" value "${value}") + string(REPLACE "[" "${_OpenBracketEscape}" value "${value}") + string(REPLACE "]" "${_CloseBracketEscape}" value "${value}") + set(${var} "${value}" PARENT_SCOPE) +endfunction() + + +# Turns placeholders back into original characters, see the top of this file. +# Modifies argument `var` in place. +function(magic_unescape_chars var) + set(value "${${var}}") + string(REPLACE "${_SemicolonEscape}" ";" value "${value}") + string(REPLACE "${_OpenBracketEscape}" "[" value "${value}") + string(REPLACE "${_CloseBracketEscape}" "]" value "${value}") + set(${var} "${value}" PARENT_SCOPE) +endfunction() + + +# Abuses knowledge of Catch2's JSON reporter output for listing tests to +# split JSON array of the test listings into a CMake list of strings, +# with each element being the JSON string of one array entry. +# +# This avoids the terrible quadratic running time of using CMake's JSON +# support to parse the JSON reporter output "properly", where the whole +# JSON array of tests is parsed again for every element. Instead, we can +# use the CMake's API to only parse the individual test's objects, which +# are usually small and only have to be reparsed fixed number of times +# (once for test names, once for labels). +# +# We process the string representing the JSON array by splitting it on +# `}<ws>*,<ws>*{` and then checking for each chunk whether it is a valid +# JSON object representing Catch2's test. If not (e.g. because we split +# on the presence of `}<ws>*,<ws>*{` inside a test name), then we append +# the next chunk to the current one and check again. And again, until +# we get back to a valid JSON. +# +# Note that to support passing the object strings back from the function, +# they will still contain the placeholders and need to be unescaped before +# further processing (e.g. sending them into CMake's JSON parsing API). +function(split_json_array json_array_var out_var) + # We have to pass the input by var name to avoid CMake processing + # the input as an arg. + set(json_in "${${json_array_var}}") + + # Strip the array brackets at the start and end of the JSON array. + # Must happen before we escape the other [] instances below from the + # actual array data. + string(REGEX REPLACE "^[ \t\r\n]*\\[" "" json_in "${json_in}") + string(REGEX REPLACE "\\][ \t\r\n]*$" "" json_in "${json_in}") + + magic_escape_chars(json_in) + + # We need to keep the whitespace around comma around, so that if we + # split inside the test object, we can reconstruct it losslessly. + string(REGEX REPLACE "(}[ \t\r\n]*)[,]([ \t\r\n]*{)" "\\1${_BoundaryEscape}\\2" json_in "${json_in}") + + # We escaped all list separators above, so now we can turn the JSON + # string into a CMake list of fragments in single pass. + string(REPLACE "${_BoundaryEscape}" ";" fragments "${json_in}") + + # And now we have to reconstruct the actual JSON structure from fragments. + set(array_elements "") + set(accumulator "") + foreach(next_fragment IN LISTS fragments) + if(accumulator) + set(accumulator "${accumulator},${next_fragment}") + else() + set(accumulator "${next_fragment}") + endif() + + # Because the fragments (might) contain invalid JSON characters due + # to escaping, we have to unescape it before checking if we can parse it. + set(maybe_json "${accumulator}") + magic_unescape_chars(maybe_json) + string(JSON unused ERROR_VARIABLE err GET "${maybe_json}" "name") + if(err STREQUAL "NOTFOUND") + list(APPEND array_elements "${accumulator}") + set(accumulator "") + endif() + endforeach() + + set(${out_var} "${array_elements}" PARENT_SCOPE) +endfunction() + # TBD: Further possible optimization is that most arguments for per-test # `prepare_command` call are constant across one invocation of # `catch_discover_tests`, and thus need checking and escaping only @@ -66,7 +191,6 @@ function(make_temp_file_path OUT_VARIABLE FALLBACK_PATH) endfunction() function(catch_discover_tests_impl) - cmake_parse_arguments( "" "" @@ -147,9 +271,10 @@ function(catch_discover_tests_impl) ) endif() - # Read the JSON output back from the output file (and then get rid of the file) + # Read the JSON output back from the output file and validate it. file(READ ${listing_output_path} listing_output) file(REMOVE ${listing_output_path}) + validate_input_noescapes(listing_output) # Prepare reporter if(reporter) @@ -205,36 +330,35 @@ function(catch_discover_tests_impl) message(FATAL_ERROR "Unsupported catch output version: '${version}'") endif() - # Speed-up reparsing by cutting away unneeded parts of JSON. + # Extract just the JSON array with tests and then split them into + # individual objects. string(JSON test_listing GET "${listing_output}" "listings" "tests") - string(JSON num_tests LENGTH "${test_listing}") + split_json_array(test_listing tests) # Exit early if no tests are detected - if(num_tests STREQUAL "0") + if(NOT tests) file(WRITE "${_CTEST_FILE}" "") return() endif() - # CMake's foreach-RANGE is inclusive, so we have to subtract 1 - math(EXPR num_tests "${num_tests} - 1") - - foreach(idx RANGE ${num_tests}) - string(LENGTH "${script}" script_len) + # Each element in the tests is JSON-string representing one test object. + # We have to parse it and then turn it into CTest script commands. + foreach(single_test IN LISTS tests) # Because appending to the same string in CMake has quadratic runtime, # we flush the script into the file periodically to avoid the worst case. + string(LENGTH "${script}" script_len) if (script_len GREATER _WriteToFileThreshold) file(APPEND "${_CTEST_FILE}" "${script}") set(script "") endif() - + # The elements are still escaped and contain JSON-invalid characters, + # they have to be unescaped before parsing them as JSON. + magic_unescape_chars(single_test) if(add_tags) - string(JSON single_test GET "${test_listing}" ${idx}) string(JSON test_tags GET "${single_test}" "tags") - string(JSON plain_name GET "${single_test}" "name") - else() - string(JSON plain_name GET "${test_listing}" ${idx} "name") endif() + string(JSON plain_name GET "${single_test}" "name") # Escape characters in test case names that would be parsed by Catch2 # Note that the \ escaping must happen FIRST! Do not change the order. |