RegexOptions.NonBacktracking with a finite match timeout misses matches on inputs over ~100k characters

[Architekt909]

Description

With RegexOptions.NonBacktracking and a finite match timeout, Regex.Matches misses matches once the input passes roughly 100,000 characters. The same pattern and input give the right answer with the backtracking engine, and with NonBacktracking plus Regex.InfiniteMatchTimeout. No RegexMatchTimeoutException is thrown, and the call returns quickly, so the timeout is not being hit. Only the result is wrong.

Reproduction Steps

using System.Text.RegularExpressions;

Console.WriteLine($"runtime {Environment.Version}");
foreach (var n in new[] { 1_000, 50_000, 150_000, 400_000 })
{
    var input = "a foo b " + new string('x', n) + " c foo d";   // "foo" appears twice
    int Count(RegexOptions o, TimeSpan t) => new Regex(@"\bfoo\b", o, t).Matches(input).Count;
    Console.WriteLine(
        $"len={input.Length,8} backtracking={Count(RegexOptions.None, Regex.InfiniteMatchTimeout)} " +
        $"nb(no timeout)={Count(RegexOptions.NonBacktracking, Regex.InfiniteMatchTimeout)} " +
        $"nb(5s)={Count(RegexOptions.NonBacktracking, TimeSpan.FromSeconds(5))}");
}

Expected behavior

All three columns report 2 for every length.

Actual behavior

Windows 11 x64, runtime 10.0.12 (Release):

len=    1016 backtracking=2 nb(no timeout)=2 nb(5s)=2
len=   50016 backtracking=2 nb(no timeout)=2 nb(5s)=2
len=  150016 backtracking=2 nb(no timeout)=2 nb(5s)=1
len=  400016 backtracking=2 nb(no timeout)=2 nb(5s)=1

Debian 13 x64 (Linux 6.19), runtime 10.0.11 (Release): identical output.

With the finite timeout, the second match (the one after the long run) is lost from about 150,000 characters on.

Regression?

Not checked against earlier versions.

Known Workarounds

Use Regex.InfiniteMatchTimeout with RegexOptions.NonBacktracking. The engine's matching time is already linear in the input length, so the timeout adds little safety there.

Configuration

• .NET 10.0.12 on Windows 11 x64, and .NET 10.0.11 on Debian 13 x64.
• Interpreted new Regex(...) (not source-generated).
• We first saw this in a source-scanning test over a ~360,000-character C# file, where \bIdentifier\b found one of two uses. Separately, on large real inputs we also saw a pattern of the form [a-z]+word report a match that the backtracking engine does not find. The minimal program above did not reproduce that second shape.

Other information

A guess at the cause, not verified in the source: the timeout path seems to process the input in pieces, and a match that begins or needs context across a piece boundary is dropped. The loss starts at about the same length on both operating systems.

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-text-regularexpressions
See info in area-owners.md if you want to be subscribed.