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.

4 files changed, 361 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.
diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index e2aad5ef..6a2028b6 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -632,6 +632,13 @@ if(CATCH_ENABLE_CMAKE_HELPER_TESTS)
       "-DCATCH_ADD_TESTS_SCRIPT=${CATCH_DIR}/extras/CatchAddTests.cmake"
       -P "${CMAKE_CURRENT_LIST_DIR}/TestScripts/DiscoverTests/TestPrepareCommand.cmake"
   )
+
+  add_test(NAME "CMakeHelper::DecomposeJsonArray"
+    COMMAND
+      "${CMAKE_COMMAND}"
+      "-DCATCH_ADD_TESTS_SCRIPT=${CATCH_DIR}/extras/CatchAddTests.cmake"
+      -P "${CMAKE_CURRENT_LIST_DIR}/TestScripts/DiscoverTests/TestDecomposeJsonArray.cmake"
+  )
 endif()
 
 foreach(reporterName # "Automake" - the simple .trs format does not support any kind of comments/metadata
diff --git a/tests/TestScripts/DiscoverTests/TestDecomposeJsonArray.cmake b/tests/TestScripts/DiscoverTests/TestDecomposeJsonArray.cmake
new file mode 100644
index 00000000..c64b4f52
--- /dev/null
+++ b/tests/TestScripts/DiscoverTests/TestDecomposeJsonArray.cmake
@@ -0,0 +1,194 @@
+# SPDX-License-Identifier: BSL-1.0
+
+# Unit tests for `split_json_array` helper in `extras/CatchAddTests.cmake`.
+#
+# Yes, we are at the stage where the script helpers need unit tests.
+#
+# Run as
+#     cmake -DCATCH_ADD_TESTS_SCRIPT=/path/to/extras/CatchAddTests.cmake \
+#           -P TestDecomposeJsonArray.cmake
+
+
+cmake_minimum_required(VERSION 3.19)
+
+if(NOT DEFINED CATCH_ADD_TESTS_SCRIPT)
+  message(FATAL_ERROR "Missing argument `CATCH_ADD_TESTS_SCRIPT`")
+endif()
+
+if(NOT EXISTS "${CATCH_ADD_TESTS_SCRIPT}")
+  message(FATAL_ERROR "Cannot find CatchAddTests.cmake at '${CATCH_ADD_TESTS_SCRIPT}'")
+endif()
+
+# Pull in the helper functions. Without `TEST_EXECUTABLE` being defined,
+# `catch_discover_tests_impl` is not called.
+include("${CATCH_ADD_TESTS_SCRIPT}")
+
+set(_failures 0)
+
+# Parses out test names from provided listings and returns them through `out_var`.
+# Semicolons in test names are escaped as `@SEMI@`.
+function(decomposed_names listing_var out_var)
+  split_json_array(${listing_var} elements)
+  set(names "")
+  foreach(element IN LISTS elements)
+    magic_unescape_chars(element)
+    string(JSON name ERROR_VARIABLE err GET "${element}" "name")
+    if(NOT err STREQUAL "NOTFOUND")
+      set(${out_var} "PARSE-ERROR" PARENT_SCOPE)
+      return()
+    endif()
+    string(REPLACE ";" "@SEMI@" name "${name}")
+    list(APPEND names "${name}")
+  endforeach()
+  set(${out_var} "${names}" PARENT_SCOPE)
+endfunction()
+
+# Assert that decomposing the provided listing returns the expected list
+# of (test) names.
+# Semicolons inside expected names must be escaped as `@SEMI@`.
+function(expect_names description listing_var expected_names)
+  decomposed_names(${listing_var} actual_names)
+  if(actual_names STREQUAL expected_names)
+    message("  [PASS] ${description}")
+  else()
+    message("  [FAIL] ${description}")
+    message("         expected: ${expected_names}")
+    message("         actual:   ${actual_names}")
+    math(EXPR _n "${_failures} + 1")
+    set(_failures "${_n}" PARENT_SCOPE)
+  endif()
+endfunction()
+
+# Assert that the tags in one decomposed element are preserved exactly.
+# Semicolons in expected tags have to be escaped as `@SEMI@`.
+function(expect_tags description listing_var element_index expected_tags)
+  split_json_array(${listing_var} elements)
+  list(GET elements ${element_index} element)
+  magic_unescape_chars(element)
+
+  string(JSON tags ERROR_VARIABLE err GET "${element}" "tags")
+  if(NOT err STREQUAL "NOTFOUND")
+    set(actual_tags "PARSE-ERROR")
+  else()
+    string(JSON tag_count LENGTH "${tags}")
+    set(actual_tags "")
+    if(tag_count GREATER 0)
+      math(EXPR last_tag "${tag_count} - 1")
+      foreach(tag_index RANGE ${last_tag})
+        string(JSON tag GET "${tags}" ${tag_index})
+        string(REPLACE ";" "@SEMI@" tag "${tag}")
+        list(APPEND actual_tags "${tag}")
+      endforeach()
+    endif()
+  endif()
+
+  if(actual_tags STREQUAL expected_tags)
+    message("  [PASS] ${description}")
+  else()
+    message("  [FAIL] ${description}")
+    message("         expected: ${expected_tags}")
+    message("         actual:   ${actual_tags}")
+    math(EXPR _n "${_failures} + 1")
+    set(_failures "${_n}" PARENT_SCOPE)
+  endif()
+endfunction()
+
+# Convenience for building a minimal-but-realistic (pretty-printed) listing.
+function(make_listing out_var)
+  set(objects "")
+  foreach(name IN LISTS ARGN)
+    # Build each object by hand; the names passed in are already JSON-safe.
+    string(APPEND objects
+      "  {\n"
+      "    \"class-name\" : \"\",\n"
+      "    \"name\" : \"${name}\",\n"
+      "    \"tags\" : [ \"[tag]\" ]\n"
+      "  },\n")
+  endforeach()
+  string(REGEX REPLACE ",\n$" "\n" objects "${objects}")
+  set(${out_var} "[\n${objects}]" PARENT_SCOPE)
+endfunction()
+
+message(STATUS "Running split_json_array correctness tests")
+
+# There are 2 main difficulties in the array decomposition that we need
+# to check for:
+# 1) Names/tags that contain the expected element boundary (`}<ws>*,<ws>*{`)
+#    inside them, and thus are split into invalid JSON.
+# 2) Names/tags that contain CMake-relevant characters (e.g. semicolon,
+#    which is list separator) and thus cause issues when processing the
+#    string splits.
+
+make_listing(listing "")
+expect_names("No tests" listing "")
+
+make_listing(listing "plain")
+expect_names("Single test" listing "plain")
+
+make_listing(listing "n1" "n2" "n3")
+expect_names("Multiple tests" listing "n1;n2;n3")
+
+make_listing(listing "before },{ after" "second")
+expect_names("The element boundary in a test name" listing "before },{ after;second")
+
+make_listing(listing "},{" "next")
+expect_names("Test name is just the boundary" listing "},{;next")
+
+make_listing(listing "a},{b},{c" "x" "y},{z")
+expect_names("Test name has multiple boundaries" listing "a},{b},{c;x;y},{z")
+
+# Listings with semicolons have to be built by hand, or CMake would mess
+# them up before decomposition.
+set(listing "[{\"name\":\"has;semicolon\",\"tags\":[]},{\"name\":\"and;another;one\",\"tags\":[]}]")
+expect_names("Test names with semicolons" listing "has@SEMI@semicolon;and@SEMI@another@SEMI@one")
+
+set(listing "[{\"name\":\"C:\\\\path\\\\file\",\"tags\":[]},{\"name\":\"plain\",\"tags\":[]}]")
+expect_names("Test names with backslashes" listing "C:\\path\\file;plain")
+
+set(listing "[{\"name\":\"compact1\",\"tags\":[]},{\"name\":\"compact2\",\"tags\":[]}]")
+expect_names("compact json" listing "compact1;compact2")
+
+make_listing(listing "Then } , { we }\t,\t{ concatenate } , { them } ,{back},{" "second")
+expect_names("Whitespace around commas in test names survive split"
+  listing "Then } , { we }\t,\t{ concatenate } , { them } ,{back},{;second")
+
+make_listing(listing "}},{{" "second")
+expect_names("Doubled up boundary braces in names" listing "}},{{;second")
+
+# Square brackets and array likes in the test names.
+set(listing "[{\"name\":\"Arrays [{},{}] wheee\",\"tags\":[\"also},{tags\",\"tag;with;semicolons\"]},{\"name\":\"n\",\"tags\":[]}]")
+expect_names("array-like substring in name" listing "Arrays [{},{}] wheee;n")
+expect_tags("boundary-like and semicolon tags are preserved" listing 0
+  "also},{tags;tag@SEMI@with@SEMI@semicolons")
+expect_tags("empty tags are preserved" listing 1 "")
+
+# Listings with square brackets have to be built by hand, or CMake would
+# mess them up before decomposition.
+set(listing "[{\"name\":\"[\",\"tags\":[]},{\"name\":\"middle\",\"tags\":[]},{\"name\":\"]\",\"tags\":[]}]")
+expect_names("unmatched square brackets" listing "[;middle;]")
+
+set(listing "[{\"name\":\"a[b]c\",\"tags\":[]},{\"name\":\"[open\",\"tags\":[]},{\"name\":\"close]\",\"tags\":[]},{\"name\":\"[]\",\"tags\":[]}]")
+expect_names("Test names with mess of brackets" listing "a[b]c;[open;close];[]")
+
+# Without careful handling, these could be evaluated as variables.
+make_listing(listing
+  "curly \${NOT_A_VAR}"
+  "env \$ENV{HOME}"
+  "cache \$CACHE{FOO}"
+  "genex \$<CONFIG>"
+  "bare \$ and \$\$ and \${ unterminated")
+expect_names("Test names with dollars and various brackets (CMake vars)" listing
+  "curly \${NOT_A_VAR};env \$ENV{HOME};cache \$CACHE{FOO};genex \$<CONFIG>;bare \$ and \$\$ and \${ unterminated")
+
+# Listings with semicolons have to be built by hand, or CMake would mess
+# them up before decomposition.
+# This is just a huge mess of everything to see if anything shakes loose.
+set(listing "[{\"name\":\"\$ENV{X};[weird]{},{ mix \$<0:no> \${VAR} };,{ }},{{\",\"tags\":[]},{\"name\":\"after\",\"tags\":[]}]")
+expect_names("combined mega-case" listing
+  "\$ENV{X}@SEMI@[weird]{},{ mix \$<0:no> \${VAR} }@SEMI@,{ }},{{;after")
+
+if(_failures GREATER 0)
+  message(FATAL_ERROR "${_failures} decomposition test(s) failed")
+endif()
+
+message(STATUS "All split_json_array correctness tests passed")
diff --git a/tests/TestScripts/DiscoverTests/register-tests.cpp b/tests/TestScripts/DiscoverTests/register-tests.cpp
index 5aec0f19..b833dba2 100644
--- a/tests/TestScripts/DiscoverTests/register-tests.cpp
+++ b/tests/TestScripts/DiscoverTests/register-tests.cpp
@@ -41,3 +41,24 @@ public:
 TEST_CASE_METHOD(TestCaseFixture, "A test case as method", "[tagstagstags]") {}
 
 TEST_CASE( "Newlines\nAnd\rOther\n\tWhitespace", "[whitespace-going-wild]" ) {}
+
+// Some JSON-like and JSON-adjacent characters and substrings in the test names/tags
+// This serves to test that the parse-json-via-string-splitting hack in
+// catch_discover_tests works properly.
+TEST_CASE( "We split on variants of },{ in name" ) {}
+TEST_CASE( "Then }\t, { we }\t,\t{ concatenate } , { them } ,{back},{" ) {}
+TEST_CASE( "}},{{" ) {}
+TEST_CASE( "Arrays [{},{}] wheee", "[also},{tags]" ) {}
+TEST_CASE( "Let's add semicolon into the mix ;},{;},{};,{}" ) {}
+TEST_CASE( "[", "[unmatched-square-bracket]" ) {}
+TEST_CASE( "]", "[unmatched-square-bracket]" ) {}
+
+// Some CMake-like special strings ($ as dereference) strings in test names.
+// This serves to test that the names of test cases are not evaluated
+// inside the catch_discover_tests.
+TEST_CASE( "Plain ${NOT_A_VAR} variable" ) {}
+TEST_CASE( "Env variable access $ENV{HOME}" ) {}
+TEST_CASE( "Cache check $CACHE{FOO}" ) {}
+TEST_CASE( "Also some generator exprs $<CONFIG> in $<1:yes> name" ) {}
+TEST_CASE( "Mess of bare $ $$ $$$ and unterminated $} ${ exprs" ) {}
+TEST_CASE( "$ENV{X};[weird]{},{ mix $<0:no> ${VAR} };,{ }},{{" ) {}