Read-only mirrors. Development, issues and pull requests are on GitHub.

summaryrefslogtreecommitdiffhomepage
path: root/extras
diff options
context:
space:
mode:
authorMartin Hořeňovský2026-07-26 13:15:10 +0200
committerMartin Hořeňovský2026-07-26 19:51:58 +0200
commit1079da4c5f5fea2a31d795bba95eacaa2f622849 (patch)
tree4f708b68ab9038d75a50e15467b3ea8182e939f1 /extras
parent60c8b878292ec4afc625a807cdc3902397a408a3 (diff)
downloadcatch3-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.cmake154
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.