<regex>: Grouping within repetition causes regex stack error

[AlexGuteniev]

Describe the bug
std::regex with satisfactory large input and certain compiler options overflows the stack

Command-line test case

d:\Temp2>type repro.cpp
#include <Windows.h>
#include <iostream>
#include <regex>
#include <string>

void regex_test()
{
    try
    {
        auto str = std::string(1000, 'a');
        auto match = std::smatch{};
        std::regex_match(str, match, std::regex("a+"));     // OK
        std::regex_match(str, match, std::regex("(?:a)+")); // stack error
    }
    catch (std::exception& ex)
    {
        std::cout << ex.what() << '\n';
    }
}

int main()
{
    bool stack_overflow_observed = false;
    __try
    {
        regex_test();
    }
    __except (GetExceptionCode() == EXCEPTION_STACK_OVERFLOW)
    {
        stack_overflow_observed = true;
    }
    if (stack_overflow_observed)
    {
        _resetstkoflw();
        std::cout << "Stack overflow was observed\n";
    }
    else
    {
        std::cout << "Stack overflow was NOT observed\n";
    }
    return 0;
}

d:\Temp2>cl /EHa /RTC1 /MDd /std:c++17 .\repro.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.27.29009.1 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

repro.cpp
Microsoft (R) Incremental Linker Version 14.27.29009.1
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:repro.exe
repro.obj

d:\Temp2>.\repro.exe
Stack overflow was observed

Expected behavior
Successful parsing or C++ exception, but not stack overflow

STL version

Microsoft Visual Studio Professional 2019 Preview
Version 16.7.0 Preview 3.1

Additional context
This item is also tracked on Developer Community as DevCom-885115 and by Microsoft-internal VSO-1054746 / AB#1054746.

See also #405

vNext note: Resolving this issue will require breaking binary compatibility. We won't be able to accept pull requests for this issue until the vNext branch is available. See #169 for more information.

[AlexGuteniev]

Boost.Regex actually can run into stack overflow and recover from it by itself. See BOOST_REGEX_RECURSIVE in its documentation. This strategy is better for performance of normal cases than avoiding stack allocation or trying to limit them to some amount.

There are actually few ways to accomplish this, and catching EXCEPTION_STACK_OVERFLOW is just one of them. Another is to call GetCurrentThreadStackLimits/SetThreadStackGuarantee and stand away from dangerously low stack.

[StephanTLavavej]

We talked about this at the weekly maintainer meeting (see #1488). We concluded that reducing the recursion limit would likely cause more problems than it "solves", so we believe that we can't make changes here until vNext.

[StephanTLavavej]

Trying to recover from stack overflow would be extremely squirrely and I am strongly opposed to such attempts. 🐿️

Alex Guteniev (@AlexGuteniev) observed that Boost.Regex dropped its "recursive" mode in 1.76.0; compare its 1.75.0 docs to 1.76.0 docs.

I believe we could avoid stack overflow issues while preserving bincompat by rewriting the header-only matching functions to traverse the NFA nodes while allocating "frames" on the heap. We can't mess with the data structure itself, but we can change how we process it. It would be a big change though.

[StephanTLavavej]

The stack overflow has been fixed, but we're throwing a regex_error(error_stack) now.