Regex Capture gives IndexOutOfRangeException on (?:){93}

[danmoseley]

Regex regex = new("@(a*)+?");
MatchCollection mc = regex.Matches("@");

foreach (Match m in mc)
{
    Console.WriteLine($"{m.Index} .. {m.Length + m.Index}");
    Console.WriteLine(m.ToString());
}

On other regex engines, like PCRE, Nim, Python, Javascript, and Golang you would get 0 .. 1

On .NET Framework this displays 1 .. 1

On .NET 6 it gives

1 .. 3
Unhandled exception. System.ArgumentOutOfRangeException: Index and length must refer to a location within the string. (Parameter 'length')
   at System.String.Substring(Int32 startIndex, Int32 length)
   at System.Text.RegularExpressions.Capture.get_Value()
   at System.Text.RegularExpressions.Capture.ToString()
   at Program.<Main>$(String[] args) in C:\Users\danmose\source\repos\ConsoleApp31\ConsoleApp31\Program.cs:line 191

@stephentoub first bug from running Nim tests.

[ghost]

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

Issue Details

---

Regex regex = new("@(a*)+?");
MatchCollection mc = regex.Matches("@");

foreach (Match m in mc)
{
    Console.WriteLine($"{m.Index} .. {m.Length + m.Index - 1}");
    Console.WriteLine(m.ToString());
}

On other regex engines, like PCRE, Nim, Python, Javascript, and Golang you would get 0 .. 1

On .NET Framework this displays 1 .. 0

On .NET 6 it gives

1 .. 2
Unhandled exception. System.ArgumentOutOfRangeException: Index and length must refer to a location within the string. (Parameter 'length')
   at System.String.Substring(Int32 startIndex, Int32 length)
   at System.Text.RegularExpressions.Capture.get_Value()
   at System.Text.RegularExpressions.Capture.ToString()
   at Program.<Main>$(String[] args) in C:\Users\danmose\source\repos\ConsoleApp31\ConsoleApp31\Program.cs:line 191

@stephentoub first bug from running Nim tests.

Author:	danmoseley
Assignees:	-
Labels:	area-System.Text.RegularExpressions, untriaged
Milestone:	-

[danmoseley]

@(a?)+? with text of @will not crash, but gives 1 .. 1 whereas other engines will give 0 .. 1

So there seems to be distinct bugs

• incorrect starting index of the match in all .NET versions
• incorrect length in .NET Core, causing a crash.

[stephentoub]

incorrect length in .NET Core, causing a crash.

Looks like a regression in .NET 5, which also exhibits this. .NET Core 3.1 outputs 1..1 like .NET Framework does.

[stephentoub]

This is actually an issue in .NET Framework 4.8 and .NET Core 3.1 as well.

The change in .NET 5 is that it recognizes that the outer loop is actually atomic (because there's nothing after it to backtrack into it). So it effectively changes the expression to instead be:

"@(?>(a*)+?)"

Try that expression with .NET Framework, and you similarly get 1..3 and an out of range exception.

[stephentoub]

(Locally I also have the final changes that switches over all compiler / source generated expressions to using the new simpler code generation (except for anything that uses RightToLeft), and with that, this correctly outputs 0..1 and no exception, so it'll end up really only being an issue for the interpreter.)

[danmoseley]

When I fuzzed I believe I only used IsMatch. Next time we should enumerate the matches also.

[joperezr]

I just tested with Preview 7 bits and seems like all 4 engines (including Interpreted) are correctly printing:

0 .. 1
@

Not sure exactly which change fixed this as it was logged some time ago, but closing as completed.

[danmoseley]

@joperezr might be worth adding as a test case if we don't have one.

[joperezr]

Good point, I'll reopen this to track that.

[stephentoub]

https://github.com/dotnet/runtime/blob/main/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/Regex.MultipleMatches.Tests.cs#L393-L422

[joperezr]

lol, that explains why after adding it I was seeing it running elsewhere in testResults.xml. I'll fix that condition instead then.

[joperezr]

so I tried re-enabling all those 3, but looks like one is still problematic:

runtime/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/Regex.MultipleMatches.Tests.cs

Lines 405 to 409 in f7d7b55

	engine, @"(?:){93}", "x", RegexOptions.None, new[]
	{
	new CaptureData("", 0, 0),
	new CaptureData("", 1, 0)
	}

This is still throwing IndexOutOfRangeException when trying to call Trackpush(). Looks like with such a large number of loops (93 in that testcase) we are failing when trying to walk back through the runtrack stack, the exception is being thrown on this line:

runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexInterpreter.cs

Line 82 in 63692cd

localruntrack[--localruntrackpos] = i1;

since at some point runtrackpos is 0 so this is trying to access to index -1

[stephentoub]

@joperezr, can this be closed again now?

Or if it's tracking a disabled test, should it be moved out of 7.0 and labeled as disabled test?

[joperezr]

it is tracking a disabled test, so I'll label and move as suggested.

[rhirano0715]

I would like to provide a comment for reference.
When I tried changing the number of repetitions and testing it, the following results were obtained.

• net9.0
  • @"(?:){0}" ～ @"(?:){25}": Success
  • @"(?:){26}": Failure
    IndexOutOfRangeException occurs (index is -1) in the following code snippet of RegexInterpreter. TrackPush2(int i1, int i2)
    

    runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexInterpreter.cs

    Line 125 in 315a2a8

    localruntrack[--localruntrackpos] = i2;

  • @"(?:){27}" ～ @"(?:){99}": Failure
    Probably, failures continue from @"(?:){100}" onwards.
    IndexOutOfRangeException occurs (index is -1) in the following code snippet of RegexInterpreter. TrackPush(int i1)
    

    runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexInterpreter.cs

    Line 78 in 315a2a8

    localruntrack[--localruntrackpos] = _codepos;

• (net48)
  • @"(?:){0}" ～ @"(?:){16}": Success
  • @"(?:){17}" ～ @"(?:){99}": Failure(IndexOutOfRangeException )
    Probably, failures continue from @"(?:){100}" onwards.

I insert the following into Regex.MultipleMatches.Tests.Matches_TestData() for testing.

                for (int i = 0; i < 100; i++)
                {
                    yield return new object[]
                    {
                        engine, @"(?:){" + i + @"}", "x", RegexOptions.None, new[]
                        {
                            new CaptureData("", 0, 0),
                            new CaptureData("", 1, 0)
                        }
                    };
                }

[rhirano0715]

The size of RegexRunner.runtrack is set to runtrackcount * 8 (runtrackcount == _code.TrackCount).
The value of runtrackcount was as follows:

• For @"(?:){0}" ~ @"(?:){1}": 3
• For @"(?:){2}" ~ @"(?:){99}": 7

It appears that the reason the index (runtrackpos) becomes negative and causes an exception from @"(?:){26}" ~ @"(?:){99}" is because the runtrack size of 7 * 8 (== 56) is not sufficient.