Skip to content

Improve the match cache optimization to support look-around and atomic groups #7931

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

Merged
merged 7 commits into from
Oct 30, 2023

Conversation

makenowjust
Copy link
Contributor

Close [Feature #19725].

https://bugs.ruby-lang.org/issues/19725

@makenowjust makenowjust mentioned this pull request Jun 12, 2023
@makenowjust makenowjust changed the title Improve the match cache optimization to support look-ahead and atomic groups Improve the match cache optimization to support look-around and atomic groups Jun 19, 2023
@nobu nobu force-pushed the memoize-on-backtrack branch from dbf34a9 to 51f68db Compare June 21, 2023 01:10
@makenowjust makenowjust force-pushed the memoize-on-backtrack branch from 51f68db to df10ebb Compare August 17, 2023 12:44
@mame mame self-requested a review September 12, 2023 08:20
The previous implementation records a match cache point on arrived this.
However, such a implementation introduced the null-loop problem; that
is, null-loops that should be matched are recorded and fail to match.
When we memoize (record) cache points on backtracking, we can avoid this
annoying problem.

Additionally, we expect this implementation makes to support look-around
operators available.
We cannot memoize atomic groups matching result in a bit array because
its matching result must be memoized with matching position.
@makenowjust makenowjust merged commit 34cb174 into ruby:master Oct 30, 2023
@makenowjust makenowjust deleted the memoize-on-backtrack branch October 30, 2023 04:10
casperisfine pushed a commit to Shopify/ruby that referenced this pull request Nov 15, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants