Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Factor positive lookaheads better into find optimizations#112107

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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
stephentoub merged 2 commits intodotnet:mainfromstephentoub:updatelookaroundopt
Feb 5, 2025

Conversation

@stephentoub
Copy link
Member

@stephentoubstephentoub commentedFeb 3, 2025•
edited
Loading

A positive lookahead at the start of a pattern can be used for determining find optimizations even when the non-zero-width portions of the pattern aren't. This helps particularly in cases where the positive lookahead contains an anchor or a literal.

Also extends the existing alternation reduction optimization to factor out anchors that begin every branch of an alternation.

As an example of how this applies, this is one of the expressions in our list:

(?=^\bset\b.*;\s*\bselect\b|^\bselect\b).*?\s+from\s+(?:[\s\(\[`\"]*([^,;\[\s\]\(\)`\"\.]*)[\s\)\]`\"]*)(?:\.[\s\(\[`\"]*([^,;\[\s\]\(\)`\"\.]*)[\s\)\]`\"]*)*

Note that the pattern begins with a positive lookahead and that what comes after it isn't particularly searchable. This leads to the following generated TryFindNextPossibleStartingPosition routine:

privateboolTryFindNextPossibleStartingPosition(ReadOnlySpan<char>inputSpan){intpos=base.runtextpos;// Any possible match is at least 6 characters.if(pos<=inputSpan.Length-6){returntrue;}// No match found.base.runtextpos=inputSpan.Length;returnfalse;}

which effectively always just returns true (as long as the input is long enough), which means we end up trying to match at most positions.

Now with the change, we get this:

privateboolTryFindNextPossibleStartingPosition(ReadOnlySpan<char>inputSpan){intpos=base.runtextpos;// Any possible match is at least 6 characters.if(pos<=inputSpan.Length-6){// The pattern leads with a beginning (\A) anchor.if(pos==0){returntrue;}}// No match found.base.runtextpos=inputSpan.Length;returnfalse;}

Note the newpos == 0 check. That happens because we will now factor in the ^ from the positive lookahead's alternation.

A positive lookahead at the start of a pattern can be used for determining find optimizations even when the non-zero-width portions of the pattern aren't. This helps particularly in cases where the positive lookahead contains an anchor or a literal.Also extends the existing alternation reduction optimization to factor out anchors that begin every branch of an alternation.
@dotnet-policy-service
Copy link
Contributor

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

Copy link
Contributor

CopilotAI left a comment

Choose a reason for hiding this comment

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

Copilot reviewed 6 out of 6 changed files in this pull request and generated no comments.

Tip: If you use Visual Studio Code, you can request a review from Copilot before you push from the "Source Control" tab.Learn more

@stephentoubstephentoub merged commit2faef6d intodotnet:mainFeb 5, 2025
85 checks passed
@stephentoubstephentoub deleted the updatelookaroundopt branchFebruary 5, 2025 22:18
grendello added a commit to grendello/runtime that referenced this pull requestFeb 6, 2025
* main: (23 commits)  add important remarks to NrbfDecoder (dotnet#111286)  docs: fix spelling grammar and missing words in clr-code-guide.md (dotnet#112222)  Consider type declaration order in MethodImpls (dotnet#111998)  Add a feature flag to not use GVM in Linq Select (dotnet#109978)  [cDAC] Implement ISOSDacInterface::GetMethodDescPtrFromIp (dotnet#110755)  Restructure JSImport/JSExport generators to share more code and utilize more Microsoft.Interop.SourceGeneration shared code (dotnet#107769)  Add more detailed explanations to control-flow RegexOpcode values (dotnet#112170)  Add repo-specific condition to labeling workflows (dotnet#112169)  Fix bad assembly when a nested exported type is marked via link.xml (dotnet#107945)  Make `CalculateAssemblyAction` virtual. (dotnet#112154)  JIT: Enable reusing profile-aware DFS trees between phases (dotnet#112198)  Add support for LDAPTLS_CACERTDIR \ TrustedCertificateDirectory (dotnet#111877)  JIT: Support custom `ClassLayout` instances with GC pointers in them (dotnet#112064)  Factor positive lookaheads better into find optimizations (dotnet#112107)  Add ImmutableCollectionsMarshal.AsMemory (dotnet#112177)  [mono] ILStrip write directly to the output filestream (dotnet#112142)  Allow the NativeAOT runtime pack to be specified as the ILC runtime package (dotnet#111876)  JIT: some reworking for conditional escape analysis (dotnet#112194)  Replace HELPER_METHOD_FRAME with DynamicHelperFrame in patchpoints (dotnet#112025)  [Android] Decouple runtime initialization and entry point execution for Android sample (dotnet#111742)  ...
@github-actionsgithub-actionsbot locked and limited conversation to collaboratorsMar 8, 2025
Sign up for freeto subscribe to this conversation on GitHub. Already have an account?Sign in.

Reviewers

Copilot code reviewCopilotCopilot left review comments

@danmoseleydanmoseleydanmoseley approved these changes

@joperezrjoperezrAwaiting requested review from joperezr

+2 more reviewers

@campersaucampersaucampersau left review comments

@steveharterstevehartersteveharter approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

@stephentoubstephentoub

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@stephentoub@campersau@danmoseley@steveharter
[8]ページ先頭
©2009-2025 Movatter.jp