Match_Timeout_Repetition_Throws(engine: NonBacktracking) timing out

[stephentoub]

This outer loop test is now running for a very long time and eventually the test suite times out. I expect this is due to 83e5cbc, and that it's doing exactly what it tried to do, which is keep execution in the inner loop as long as possible. That would mean, however, that we wouldn't exit out into the outer loop frequently enough to hit the timeout check:

runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs

Lines 786 to 821 in d9eafd0

	// Now run the DFA or NFA traversal from the current point using the current state.
	int finalStatePosition;
	int findResult = currentState.NfaState is not null ?
	FindFinalStatePositionDeltas<NfaStateHandler>(builder, input, ref i, ref currentState, ref matchLength, out finalStatePosition) :
	FindFinalStatePositionDeltas<DfaStateHandler>(builder, input, ref i, ref currentState, ref matchLength, out finalStatePosition);
	// If we reached a final or deadend state, we're done.
	if (findResult > 0)
	{
	return finalStatePosition;
	}
	// We're not at an end state, so we either ran out of input (in which case no match exists), hit an initial state (in which case
	// we want to loop around to apply our initial state processing logic and optimizations), or failed to transition (which should
	// only happen if we were in DFA mode and need to switch over to NFA mode). If we exited because we hit an initial state,
	// find result will be 0, otherwise negative.
	if (findResult < 0)
	{
	if ((uint)i >= (uint)input.Length)
	{
	// We ran out of input. No match.
	break;
	}
	// We failed to transition. Upgrade to DFA mode.
	Debug.Assert(currentState.DfaState is not null);
	NfaMatchingState nfaState = perThreadData.NfaState;
	nfaState.InitializeFrom(currentState.DfaState);
	currentState = new CurrentState(nfaState);
	}
	// Check for a timeout before continuing.
	if (_checkTimeout)
	{
	DoCheckTimeout(timeoutOccursAt);
	}

cc: @olsaarik

[ghost]

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

Issue Details

---

This outer loop test is now running for a very long time and eventually the test suite times out. I expect this is due to 83e5cbc, and that it's doing exactly what it tried to do, which is keep execution in the inner loop as long as possible. That would mean, however, that we wouldn't exit out into the outer loop frequently enough to hit the timeout check:

runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs

Lines 786 to 821 in d9eafd0

	// Now run the DFA or NFA traversal from the current point using the current state.
	int finalStatePosition;
	int findResult = currentState.NfaState is not null ?
	FindFinalStatePositionDeltas<NfaStateHandler>(builder, input, ref i, ref currentState, ref matchLength, out finalStatePosition) :
	FindFinalStatePositionDeltas<DfaStateHandler>(builder, input, ref i, ref currentState, ref matchLength, out finalStatePosition);
	// If we reached a final or deadend state, we're done.
	if (findResult > 0)
	{
	return finalStatePosition;
	}
	// We're not at an end state, so we either ran out of input (in which case no match exists), hit an initial state (in which case
	// we want to loop around to apply our initial state processing logic and optimizations), or failed to transition (which should
	// only happen if we were in DFA mode and need to switch over to NFA mode). If we exited because we hit an initial state,
	// find result will be 0, otherwise negative.
	if (findResult < 0)
	{
	if ((uint)i >= (uint)input.Length)
	{
	// We ran out of input. No match.
	break;
	}
	// We failed to transition. Upgrade to DFA mode.
	Debug.Assert(currentState.DfaState is not null);
	NfaMatchingState nfaState = perThreadData.NfaState;
	nfaState.InitializeFrom(currentState.DfaState);
	currentState = new CurrentState(nfaState);
	}
	// Check for a timeout before continuing.
	if (_checkTimeout)
	{
	DoCheckTimeout(timeoutOccursAt);
	}

cc: @olsaarik

Author:	stephentoub
Assignees:	-
Labels:	area-System.Text.RegularExpressions
Milestone:	7.0.0

[olsaarik]

Ok seems we'll need to introduce some equivalent of the previous "leeway" thing to pop out of the inner loop occasionally. The check for "did we reach the end of input" could just additionally check if the inner loop was actually given the full length of the input and if not just loop back (but skip the NFA promotion).

[olsaarik]

I'll be making changes to these matching loops in the PR after #66038, so I can fix it at the same time.