Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Test failure System.Text.RegularExpressions.Tests.RegexMatchTests.Match_VaryingLengthStrings_Huge #65289

Closed
VincentBu opened this issue Feb 14, 2022 · 17 comments
Assignees
Labels
arch-x86 area-System.Text.RegularExpressions disabled-test The test is disabled in source code against the issue os-windows
Milestone

Comments

@VincentBu
Copy link
Contributor

Run: runtime-libraries-coreclr outerloop 20220213.4

Failed test:

net7.0-windows-Release-x86-CoreCLR_release-Windows.Amd64.Server2022.Open

- System.Text.RegularExpressions.Tests.RegexMatchTests.Match_VaryingLengthStrings_Huge(engine: NonBacktracking)

Error message:

System.OutOfMemoryException : Exception of type 'System.OutOfMemoryException' was thrown.


Stack trace
   at System.Array.Resize[T](T[]& array, Int32 newSize) in /_/src/libraries/System.Private.CoreLib/src/System/Array.cs:line 43
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexBuilder`1.MakeNewState(DfaMatchingState`1 state) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexBuilder.cs:line 461
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexBuilder`1.MkState(SymbolicRegexNode`1 node, UInt32 prevCharKind, Boolean antimirov) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexBuilder.cs:line 415
   at System.Text.RegularExpressions.Symbolic.DfaMatchingState`1.Next(T minterm) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/DfaMatchingState.cs:line 114
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexMatcher`1.CreateNewTransition(DfaMatchingState`1 state, TSetType minterm, Int32 offset) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs:line 455
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexMatcher`1.FindEndPosition(ReadOnlySpan`1 input, Int32 i) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs:line 576
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexMatcher`1.FindMatch(Boolean isMatch, ReadOnlySpan`1 input, Int32 startat, PerThreadData perThreadData) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs:line 551
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexRunnerFactory.Runner`1.Go() in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexRunnerFactory.cs:line 101
   at System.Text.RegularExpressions.RegexRunner.Scan(Regex regex, String text, Int32 textbeg, Int32 textend, Int32 textstart, Int32 prevlen, Boolean quick, TimeSpan timeout) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexRunner.cs:line 171
   at System.Text.RegularExpressions.Regex.Run(Boolean quick, Int32 prevlen, String input, Int32 beginning, Int32 length, Int32 startat) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.cs:line 369
   at System.Text.RegularExpressions.Regex.Match(String input) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.Match.cs:line 84
   at System.Text.RegularExpressions.Regex.Match(String input, String pattern, RegexOptions options) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.Match.cs:line 68
   at System.Text.RegularExpressions.Tests.RegexMatchTests.Match(RegexEngine engine, String pattern, String input, RegexOptions options, Regex r, Int32 beginning, Int32 length, Boolean expectedSuccess, String expectedValue) in /_/src/libraries/System.Text.RegularExpressions/tests/Regex.Match.Tests.cs:line 859
   at System.Text.RegularExpressions.Tests.RegexMatchTests.Match_VaryingLengthStrings(RegexEngine engine, RegexOptions options, Int32 length) in /_/src/libraries/System.Text.RegularExpressions/tests/Regex.Match.Tests.cs:line 905
   at System.Text.RegularExpressions.Tests.RegexMatchTests.Match_VaryingLengthStrings_Huge(RegexEngine engine) in /_/src/libraries/System.Text.RegularExpressions/tests/Regex.Match.Tests.cs:line 914
--- End of stack trace from previous location ---
@dotnet-issue-labeler dotnet-issue-labeler bot added the untriaged New issue has not been triaged by the area owner label Feb 14, 2022
@ghost
Copy link

ghost commented Feb 14, 2022

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

Issue Details

Run: runtime-libraries-coreclr outerloop 20220213.4

Failed test:

net7.0-windows-Release-x86-CoreCLR_release-Windows.Amd64.Server2022.Open

- System.Text.RegularExpressions.Tests.RegexMatchTests.Match_VaryingLengthStrings_Huge(engine: NonBacktracking)

Error message:

System.OutOfMemoryException : Exception of type 'System.OutOfMemoryException' was thrown.


Stack trace
   at System.Array.Resize[T](T[]& array, Int32 newSize) in /_/src/libraries/System.Private.CoreLib/src/System/Array.cs:line 43
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexBuilder`1.MakeNewState(DfaMatchingState`1 state) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexBuilder.cs:line 461
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexBuilder`1.MkState(SymbolicRegexNode`1 node, UInt32 prevCharKind, Boolean antimirov) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexBuilder.cs:line 415
   at System.Text.RegularExpressions.Symbolic.DfaMatchingState`1.Next(T minterm) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/DfaMatchingState.cs:line 114
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexMatcher`1.CreateNewTransition(DfaMatchingState`1 state, TSetType minterm, Int32 offset) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs:line 455
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexMatcher`1.FindEndPosition(ReadOnlySpan`1 input, Int32 i) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs:line 576
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexMatcher`1.FindMatch(Boolean isMatch, ReadOnlySpan`1 input, Int32 startat, PerThreadData perThreadData) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs:line 551
   at System.Text.RegularExpressions.Symbolic.SymbolicRegexRunnerFactory.Runner`1.Go() in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexRunnerFactory.cs:line 101
   at System.Text.RegularExpressions.RegexRunner.Scan(Regex regex, String text, Int32 textbeg, Int32 textend, Int32 textstart, Int32 prevlen, Boolean quick, TimeSpan timeout) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexRunner.cs:line 171
   at System.Text.RegularExpressions.Regex.Run(Boolean quick, Int32 prevlen, String input, Int32 beginning, Int32 length, Int32 startat) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.cs:line 369
   at System.Text.RegularExpressions.Regex.Match(String input) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.Match.cs:line 84
   at System.Text.RegularExpressions.Regex.Match(String input, String pattern, RegexOptions options) in /_/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.Match.cs:line 68
   at System.Text.RegularExpressions.Tests.RegexMatchTests.Match(RegexEngine engine, String pattern, String input, RegexOptions options, Regex r, Int32 beginning, Int32 length, Boolean expectedSuccess, String expectedValue) in /_/src/libraries/System.Text.RegularExpressions/tests/Regex.Match.Tests.cs:line 859
   at System.Text.RegularExpressions.Tests.RegexMatchTests.Match_VaryingLengthStrings(RegexEngine engine, RegexOptions options, Int32 length) in /_/src/libraries/System.Text.RegularExpressions/tests/Regex.Match.Tests.cs:line 905
   at System.Text.RegularExpressions.Tests.RegexMatchTests.Match_VaryingLengthStrings_Huge(RegexEngine engine) in /_/src/libraries/System.Text.RegularExpressions/tests/Regex.Match.Tests.cs:line 914
--- End of stack trace from previous location ---
Author: VincentBu
Assignees: -
Labels:

arch-x86, area-System.Text.RegularExpressions, os-windows

Milestone: -

@VincentBu VincentBu added the blocking-outerloop Blocking the 'runtime-coreclr outerloop' and 'runtime-libraries-coreclr outerloop' runs label Feb 14, 2022
@stephentoub
Copy link
Member

cc: @olsaarik

@olsaarik
Copy link
Contributor

I'll take a look. This looks like the state space has blown up, which the Antimirov mode should prevent. Maybe something I did has disabled it.

@olsaarik
Copy link
Contributor

I think I know why this is failing. The pattern is just a 100.000 characters long string and the behavior of that is the same in both Brzozowski and Antimirov mode: it expands to a string of 100.000 states checking for each character in turn. Moreover, each phase of matching creates its own set of 100.000 states (for the .* version, the reverse version and finally the original pattern). The out-of-memory is happening some time in the third phase of matching.

The thing that changed was that now there's two arrays for transitions that get expanded whenever new states are added. This should be avoided by decoupling the capturing-tracking and traditional automata state spaces. I'll do the fix.

@VincentBu
Copy link
Contributor Author

Failed again in: runtime-libraries-coreclr outerloop 20220418.8

Failed test:

net7.0-windows-Release-x86-CoreCLR_release-Windows.Amd64.Server2022.Open

- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Compiled, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"tr-TR\", options: None)

Error message:

System.OutOfMemoryException : Exception of type 'System.OutOfMemoryException' was thrown.


Stack trace
   at System.Runtime.Loader.AssemblyLoadContext.<InitializeAssemblyLoadContext>g____PInvoke__|0_0(IntPtr ptrAssemblyLoadContext, Int32 fRepresentsTPALoadContext, Int32 isCollectible)
   at System.Runtime.Loader.AssemblyLoadContext..ctor(Boolean representsTPALoadContext, Boolean isCollectible, String name)
   at System.Text.RegularExpressions.Tests.RegexGeneratorHelper.SourceGenRegexAsync(ValueTuple`3[] regexes, CancellationToken cancellationToken)
   at System.Text.RegularExpressions.Tests.RegexGeneratorHelper.SourceGenRegexAsync(String pattern, Nullable`1 options, Nullable`1 matchTimeout, CancellationToken cancellationToken)
   at System.Text.RegularExpressions.Tests.RegexHelpers.GetRegexAsync(RegexEngine engine, String pattern, Nullable`1 options, Nullable`1 matchTimeout)
   at System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.<>c__DisplayClass10_0.<<Unicode_IgnoreCase_Tests>g__ValidateMatch|0>d.MoveNext()
--- End of stack trace from previous location ---
   at System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(RegexEngine engine, String culture, RegexOptions options)
--- End of stack trace from previous location ---

@stephentoub
Copy link
Member

Failed again

This is a different test using a different regex engine.

@VincentBu
Copy link
Contributor Author

Failed again in: runtime-libraries-coreclr outerloop 20220426.3

Failed test:

net7.0-windows-Release-x64-CoreCLR_release-(Windows.Nano.1809.Amd64.Open)windows.10.amd64.serverrs5.open@mcr.microsoft.com/dotnet-buildtools/prereqs:nanoserver-1809-helix-amd64-08e8e40-20200107182504

- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: NonBacktracking, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Compiled, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Interpreter, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"tr-TR\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: NonBacktracking, culture: \"tr-TR\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Compiled, culture: \"tr-TR\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Interpreter, culture: \"tr-TR\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"EN-US\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: NonBacktracking, culture: \"EN-US\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Compiled, culture: \"EN-US\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Interpreter, culture: \"EN-US\", options: None)

net7.0-windows-Release-x64-CoreCLR_release-Windows.81.Amd64.Open

- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: NonBacktracking, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Compiled, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Interpreter, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"tr-TR\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: *

net7.0-windows-Release-x86-CoreCLR_release-Windows.7.Amd64.Open

- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: NonBacktracking, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Compiled, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: Interpreter, culture: \"AZ\", options: None)
- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: *

Error message:

Assert.True() Failure
Expected: True
Actual:   False


Stack trace
   at System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.<>c__DisplayClass9_0.<<Unicode_IgnoreCase_Tests>g__ValidateMatch|0>d.MoveNext() in /_/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexIgnoreCaseTests.cs:line 181
--- End of stack trace from previous location ---
   at System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(RegexEngine engine, String culture, RegexOptions options) in /_/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexIgnoreCaseTests.cs:line 170
--- End of stack trace from previous location ---

Failed test:

net7.0-windows-Release-x86-CoreCLR_release-Windows.Amd64.Server2022.Open

- System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(engine: SourceGenerated, culture: \"AZ\", options: None)

Error message:

System.OutOfMemoryException : Exception of type 'System.OutOfMemoryException' was thrown.


Stack trace
   at System.Runtime.Loader.AssemblyLoadContext.LoadFromStream(IntPtr ptrNativeAssemblyBinder, IntPtr ptrAssemblyArray, Int32 iAssemblyArrayLen, IntPtr ptrSymbols, Int32 iSymbolArrayLen, ObjectHandleOnStack retAssembly)
   at System.Runtime.Loader.AssemblyLoadContext.InternalLoad(ReadOnlySpan`1 arrAssembly, ReadOnlySpan`1 arrSymbols)
   at System.Runtime.Loader.AssemblyLoadContext.LoadFromStream(Stream assembly, Stream assemblySymbols)
   at System.Text.RegularExpressions.Tests.RegexGeneratorHelper.SourceGenRegexAsync(ValueTuple`3[] regexes, CancellationToken cancellationToken)
   at System.Text.RegularExpressions.Tests.RegexGeneratorHelper.SourceGenRegexAsync(String pattern, Nullable`1 options, Nullable`1 matchTimeout, CancellationToken cancellationToken)
   at System.Text.RegularExpressions.Tests.RegexHelpers.GetRegexAsync(RegexEngine engine, String pattern, Nullable`1 options, Nullable`1 matchTimeout)
   at System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.<>c__DisplayClass9_0.<<Unicode_IgnoreCase_Tests>g__ValidateMatch|0>d.MoveNext()
--- End of stack trace from previous location ---
   at System.Text.RegularExpressions.Tests.RegexIgnoreCaseTests.Unicode_IgnoreCase_Tests(RegexEngine engine, String culture, RegexOptions options)
--- End of stack trace from previous location ---

@joperezr joperezr added this to the 7.0.0 milestone May 4, 2022
@ghost ghost removed the untriaged New issue has not been triaged by the area owner label May 4, 2022
@VincentBu

This comment was marked as off-topic.

@VincentBu

This comment was marked as off-topic.

@VincentBu

This comment was marked as off-topic.

@stephentoub
Copy link
Member

@VincentBu, all of these Unicode_IgnoreCase_Tests failures should be #69406 rather than this issue.

@joperezr
Copy link
Member

My bad, that issue has fell under my radar. I will work on it tomorrow to mitigate all those failures.

@VincentBu
Copy link
Contributor Author

@stephentoub, I leave a new comment under #69406 and hide those off-topic comments in this thread.

@stephentoub
Copy link
Member

Thanks

@joperezr joperezr added the disabled-test The test is disabled in source code against the issue label Jul 18, 2022
@danmoseley
Copy link
Member

@joperezr if the test is disabled, we can remove the blocking label right?

@joperezr joperezr removed the blocking-outerloop Blocking the 'runtime-coreclr outerloop' and 'runtime-libraries-coreclr outerloop' runs label Jul 22, 2022
@joperezr
Copy link
Member

Yes 😄. Removed.

@joperezr
Copy link
Member

joperezr commented Aug 2, 2022

This test is only disabled on .NET Framework now, and seems to be fine on the rest of the frameworks and engines, so I'll go ahead and close this for now.

@joperezr joperezr closed this as completed Aug 2, 2022
@ghost ghost locked as resolved and limited conversation to collaborators Sep 1, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
arch-x86 area-System.Text.RegularExpressions disabled-test The test is disabled in source code against the issue os-windows
Projects
None yet
Development

No branches or pull requests

5 participants