Skip to content

Fix stack overflow from start set calculation #71842

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.

Sign up for GitHub

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

Jump to bottom
Merged
olsaarik merged 7 commits into from
Jul 8, 2022
Merged

Fix stack overflow from start set calculation #71842

olsaarik merged 7 commits into from
Jul 8, 2022

Conversation

@olsaarik
Copy link
Contributor

@olsaarik olsaarik commented Jul 8, 2022 •
edited
Loading

This fixes #71808, which was caused by a change I introduced in #71234 making a calculation for the possible starting characters of matches be top-down recursive instead of bottom-up.

The bottom-up computation is re-introduced with one improvement: instead of a separate field for the start set, the set field for Singleton nodes is re-used, since for those the start set coincides with the set. This also allowed making the field non-nullable.

@ghost ghost assigned olsaarik Jul 8, 2022
@ghost
Copy link

ghost commented Jul 8, 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

This fixes #71808, which was caused by a change I introduced in #71234 making a calculation for the possible starting characters of matches be top-down recursive instead of bottom-up.

The bottom-up computation is re-introduced with one improvement: instead of a separate field for the start set, the set field for Singleton nodes is re-used, since for those the start set coincides with the set. This also allowed making the field non-nullable, which is preferable in the common case where the TSet type is ulong.

Author: olsaarik
Assignees: -
Labels:

area-System.Text.RegularExpressions
Milestone: -

@olsaarik
Copy link
Contributor Author

olsaarik commented Jul 8, 2022

Still some semantic bug here.

stephentoub
stephentoub approved these changes Jul 8, 2022
View reviewed changes
Copy link
Member

@stephentoub stephentoub left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks!

@stephentoub
Copy link
Member

stephentoub commented Jul 8, 2022

Still some semantic bug here.

Meaning it's still stack overflowing? Or some other test is going to fail?

@olsaarik
Copy link
Contributor Author

olsaarik commented Jul 8, 2022

Still some semantic bug here.

Meaning it's still stack overflowing? Or some other test is going to fail?

Stack overflow is fixed, but something around anchor handling broke. Debugging.

@olsaarik
Copy link
Contributor Author

olsaarik commented Jul 8, 2022

The bug (both old and new) should be fixed now. All tests pass locally for me now.

@olsaarik olsaarik merged commit 5c33f2b into dotnet:main Jul 8, 2022
@olsaarik olsaarik deleted the fix-startset branch July 8, 2022 21:27
@olsaarik olsaarik mentioned this pull request Jul 8, 2022
Merged
@ghost ghost locked as resolved and limited conversation to collaborators Aug 8, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

@stephentoub stephentoub stephentoub approved these changes

Assignees

@olsaarik olsaarik

Labels

area-System.Text.RegularExpressions

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

RegexMatchTests.StressTestDeepNestingOfLoops / StressTestDeepNestingOfConcat tests stack overflowing

2 participants

@olsaarik @stephentoub