impl: fix prefix literal matching bug#984
Merged
BurntSushi merged 1 commit intomasterfrom Apr 21, 2023
Merged
Conversation
4a75247 to
cad47d7
Compare
This commit fixes a bug where it was possible to report a match where
none existed. Basically, in the current regex crate, it just cannot deal
with a mixture of look-around assertions in the prefix of a pattern and
prefix literal optimizations. Before 1.8, this was handled by simply
refusing to extract literals in that case. But in 1.8, with a rewrite of
the literal extractor, literals are now extracted for patterns like
this:
(?i:(?:\b|_)win(?:32|64|dows)?(?:\b|_))
So in 1.8, since it was still using the old engines that can't deal with
this, I added some extra logic to throw away any extracted prefix
literals if a look-around assertion occurred in the prefix of the
pattern. The problem is that the logic I used was "always occurs in the
prefix of the pattern" instead of "may occur in the prefix of the
pattern." In the pattern above, it's the latter case. So it slipped by
and the regex engine tried to use the prefix literals to accelerat the
search. This in turn caused mishandling of the `\b` and led to a false
positive match.
The specific reason why the current regex engines can't deal with this
is because they weren't designed to handle searches that took the
surrounding context into account when resolving look-around assertions.
It was a pretty big oversight on my part many years ago.
The new engines we'll be migrating to Real Soon Now don't have this
problem and can deal with the prefix literal optimizations while
correctly handling look-around assertions in the prefix.
Fixes #981
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This commit fixes a bug where it was possible to report a match where none existed. Basically, in the current regex crate, it just cannot deal with a mixture of look-around assertions in the prefix of a pattern and prefix literal optimizations. Before 1.8, this was handled by simply refusing to extract literals in that case. But in 1.8, with a rewrite of the literal extractor, literals are now extracted for patterns like this:
So in 1.8, since it was still using the old engines that can't deal with this, I added some extra logic to throw away any extracted prefix literals if a look-around assertion occurred in the prefix of the pattern. The problem is that the logic I used was "always occurs in the prefix of the pattern" instead of "may occur in the prefix of the pattern." In the pattern above, it's the latter case. So it slipped by and the regex engine tried to use the prefix literals to accelerat the search. This in turn caused mishandling of the
\band led to a false positive match.The specific reason why the current regex engines can't deal with this is because they weren't designed to handle searches that took the surrounding context into account when resolving look-around assertions. It was a pretty big oversight on my part many years ago.
The new engines we'll be migrating to Real Soon Now don't have this problem and can deal with the prefix literal optimizations while correctly handling look-around assertions in the prefix.
Fixes #981