`<regex>`: `regex_search()` throws `regex_error(error_complexity)` with an unwisely written pattern

[StephanTLavavej]

Related to #6347.

This was reported by the compiler back-end team, reduced from an important test case. This was previously accepted (MSVC Build Tools 14.50 and earlier) with regex_search() returning false (the line has been deliberately changed to contain total_WOOF_pushes so total_heap_pushes won't be found). Now with MSVC Build Tools 14.51 and later, it is rejected with a complexity exception.

D:\GitHub\STL\out\x64>type regex_repro.cpp

#include <print>
#include <regex>
#include <string>
using namespace std;

int main() {
    const regex rx(R"(.*total_heap_pushes\s*:\s*(\d+) .*)");

    const string line = "Router Stats: total_nets_routed: 113175 "
                        "total_connections_routed: 437370 "
                        "total_WOOF_pushes: 313639277 "
                        "total_heap_pops: 35866777 "
                        "total_internal_heap_pushes: 0 "
                        "total_internal_heap_pops: 0 "
                        "total_external_heap_pushes: 313639277 "
                        "total_external_heap_pops: 35866777 "
                        "total_external_SOURCE_pushes: 379297 "
                        "total_external_SOURCE_pops: 379297 "
                        "total_internal_SOURCE_pushes: 0 "
                        "total_internal_SOURCE_pops: 0 "
                        "rt_node_SOURCE_pushes: 379297 "
                        "rt_node_SOURCE_high_fanout_pushes: 3797 "
                        "rt_node_SOURCE_entire_tree_pushes: 375500 "
                        "total_external_SINK_pushes: 3488243 "
                        "total_external_SINK_pops: 3260194 "
                        "total_internal_SINK_pushes: 0 "
                        "total_internal_SINK_pops: 0 "
                        "rt_node_SINK_pushes: 0 "
                        "rt_node_SINK_high_fanout_pushes: 0 "
                        "rt_node_SINK_entire_tree_pushes: 0 "
                        "total_external_IPIN_pushes: 5501600 "
                        "total_external_IPIN_pops: 3585046 "
                        "total_internal_IPIN_pushes: 0 "
                        "total_internal_IPIN_pops: 0 "
                        "rt_node_IPIN_pushes: 0 "
                        "rt_node_IPIN_high_fanout_pushes: 0 "
                        "rt_node_IPIN_entire_tree_pushes: 0 "
                        "total_external_OPIN_pushes: 14718566 "
                        "total_external_OPIN_pops: 8542877 "
                        "total_internal_OPIN_pushes: 0 "
                        "total_internal_OPIN_pops: 0 "
                        "rt_node_OPIN_pushes: 342094 "
                        "rt_node_OPIN_high_fanout_pushes: 8165 "
                        "rt_node_OPIN_entire_tree_pushes: 333929 "
                        "total_external_CHANX_pushes: 143852606 "
                        "total_external_CHANX_pops: 10396956 "
                        "total_internal_CHANX_pushes: 0 "
                        "total_internal_CHANX_pops: 0 "
                        "rt_node_CHANX_pushes: 2213020 "
                        "rt_node_CHANX_high_fanout_pushes: 482509 "
                        "rt_node_CHANX_entire_tree_pushes: 1730511 "
                        "total_external_CHANY_pushes: 145698965 "
                        "total_external_CHANY_pops: 9702407 "
                        "total_internal_CHANY_pushes: 0 "
                        "total_internal_CHANY_pops: 0 "
                        "rt_node_CHANY_pushes: 2442282 "
                        "rt_node_CHANY_high_fanout_pushes: 589528 "
                        "rt_node_CHANY_entire_tree_pushes: 1852754 "
                        "total_number_of_adding_all_rt: 8814821 "
                        "total_number_of_adding_high_fanout_rt: 62167 "
                        "total_number_of_adding_all_rt_from_calling_high_fanout_rt: 41981 ";

    try {
        const bool found = regex_search(line, rx);
        println("regex_search() returned {}.", found);
    } catch (const regex_error& re) {
        println("{}", re.what());
    }
}

D:\GitHub\STL\out\x64>cl /EHsc /nologo /W4 /std:c++latest /MTd /Od regex_repro.cpp
regex_repro.cpp

D:\GitHub\STL\out\x64>regex_repro
regex_error(error_complexity): The complexity of an attempted match against a regular expression exceeded a pre-set level.

In this case, telling the user to fix their regex is not especially feasible. (The initial ".*" used with a regex_search() is bad and should feel bad.) I would like to retune the limits to accept this case, while still guarding against severely pathological regex DoS scenarios.

[luciansmith]

I'm experiencing a similar problem: a regex that worked on VS2022 is now throwing regex_error(error_complexity) with VS2026. (The regex in question is from maddy, a markdown-to-html converter.)

Maddy sends its text through successive regex converters; this example string fails in the 'StrongParser (underscores)' phase, since there are too many underscores in the text it gets. Thanks to Claude for extracting the various regex's and putting together this more compact example. (The original input is from BioModel 12, for what it's worth.)

#include <chrono>
#include <iostream>
#include <regex>
#include <string>
#include <vector>

namespace {

struct Stage
{
  const char* name;
  std::regex pattern;
  std::string replacement;
};

bool runStage(const Stage& stage, std::string& line)
{
  try
  {
    line = std::regex_replace(line, stage.pattern, stage.replacement);
    return true;
  }
  catch (const std::regex_error& e)
  {
    std::cout << "THREW: regex_error in " << stage.name << ": " << e.what() << "\n";
    return false;
  }
}

} // namespace

int main()
{
  std::string line =
      "( [KISAO_0000035](http://identifiers.org/biomodels.kisao/KISAO_0000035 \"Access to: KISAO_0000035\") ) with continuous variables ( [KISAO_0000018](http://identifiers.org/biomodels.kisao/KISAO_0000018 \"Access to: KISAO_0000018\") ). One sample algorithm to use is the CVODE solver ( [KISAO_0000019](http://identifiers.org/biomodels.kisao/KISAO_0000019 \"Access to: KISAO_0000019\") ). Second, one could simulate the system using Gillespie's direct method ( [KISAO_0000029](http://identifiers.org/biomodels.kisao/KISAO_0000029 \"Access to: KISAO_0000029\") ), which is a stochastic method ( [KISAO_0000036](http://identifiers.org/biomodels.kisao/KISAO_0000036 \"Access to: KISAO_0000036\") ) supporting adaptive timesteps ( [KISAO_0000041](http://identifiers.org/biomodels.kisao/KISAO_0000041 \"Access to: KISAO_0000041\") ) and using discrete variables ( [KISAO_0000016](http://identifiers.org/biomodels.kisao/KISAO_0000016 \"Access to: KISAO_0000016\") ).";

  std::vector<Stage> stages = {
    {"ImageParser",
     std::regex(R"(\!\[([^\]]*)\]\(([^\]]*)\))"),
     "<img src=\"$2\" alt=\"$1\"/>"},
    {"LinkParser (titled)",
     std::regex(R"(\[([^\]]*)\]\( *([^)^ ^"]*) *\"([^\"]*)\" *\))"),
     "<a href=\"$2\" title=\"$3\">$1</a>"},
    {"LinkParser (untitled)",
     std::regex(R"(\[([^\]]*)\]\( *([^)^ ^"]*) *\))"),
     "<a href=\"$2\">$1</a>"},
    {"StrongParser (asterisk)",
     std::regex(R"((?!.*`.*|.*<code>.*)\*\*(?![\s])(?!.*`.*|.*<\/code>.*)(.*?[^\s])\*\*(?!.*`.*|.*<\/code>.*))"),
     "<strong>$1</strong>"},
    {"StrongParser (underscore)",
     std::regex(R"((?!.*`.*|.*<code>.*)\b(_*)__(?![\s_])(?!.*`.*|.*<\/code>.*)(.*?[^\s])__(_*)\b(?!.*`.*|.*<\/code>.*))"),
     "$1<strong>$2</strong>$3"},
    {"EmphasizedParser",
     std::regex(R"((?!.*`.*|.*<code>.*)\b(_*)_(?![\s_])(?!.*`.*|.*<\/code>.*)(.*?[^\s])_(_*)\b(?!.*`.*|.*<\/code>.*))"),
     "$1<em>$2</em>$3"},
    {"StrikeThroughParser",
     std::regex(R"((?!.*`.*|.*<code>.*)\~\~(?!.*`.*|.*<\/code>.*)([^\~]*)\~\~(?!.*`.*|.*<\/code>.*))"),
     "<s>$1</s>"},
    {"InlineCodeParser",
     std::regex("`([^`]*)`"),
     "<code>$1</code>"},
    {"ItalicParser",
     std::regex(R"((?!.*`.*|.*<code>.*)\*(?!.*`.*|.*<\/code>.*)([^\*]*)\*(?!.*`.*|.*<\/code>.*))"),
     "<i>$1</i>"},
    {"BreakLineParser",
     std::regex(R"((\r\n|\r))"),
     "<br>"},
  };

  for (const auto& stage : stages)
  {
    auto start = std::chrono::steady_clock::now();
    bool ok = runStage(stage, line);
    auto elapsedMs = std::chrono::duration_cast<std::chrono::milliseconds>(
      std::chrono::steady_clock::now() - start
    ).count();
    std::cout << stage.name << ": " << (ok ? "ok" : "THREW") << " (" << elapsedMs << " ms)\n";
    if (!ok)
    {
      return 42;
    }
  }

  std::cout << "NO_THROW: full runLineParser pipeline succeeded (" << line.size() << " chars)\n";
  return 0;
}