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

Jump to bottom

regexp: Scan the input string backward for patterns ending in $ #21743

Open
sylvinus opened this issue Sep 2, 2017 · 4 comments
Open

regexp: Scan the input string backward for patterns ending in $ #21743

sylvinus opened this issue Sep 2, 2017 · 4 comments
Labels
help wanted NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Unplanned

Comments

@sylvinus
Copy link
Contributor

sylvinus commented Sep 2, 2017

As suggested by @rsc:

It seems clear that we should handle patterns ending in $, like \.(jpe?g|gif)$, by scanning the string backward, which cuts the processing from O(n) to O(1) for an input of size n. That's easy to add to the existing matchers and doesn't need to be limited to fixed-size patterns.

I'm working on a CL to implement it for strings and byte slices.
@odeke-em
Copy link
Member

odeke-em commented Sep 3, 2017

@sylvinus thank you for creating the issue and for working on the CL. For posterity, I kindly wanted to ask if you could quote/provide the reference e.g with a link or so. This way, everyone interested in the issue can refer back to it and have context of the discussion.

@sylvinus
Copy link
Contributor Author

sylvinus commented Sep 3, 2017

Hi @odeke-em! Not sure what you mean because I've already included a link to his comment in this issue?

@odeke-em
Copy link
Member

odeke-em commented Sep 3, 2017

Sorry about that! I didn't see #21463 (comment) as the hyperlink to suggested. Thanks for giving me a double check, I'll def go sleep, it is 5:29AM and am not clearly observing things :)

@ianlancetaylor ianlancetaylor added Performance help wanted NeedsFix The path to resolution is known, but the work has not been done. labels Mar 29, 2018
@ianlancetaylor ianlancetaylor added this to the Unplanned milestone Mar 29, 2018
@gopherbot
Copy link

Change https://golang.org/cl/171417 mentions this issue: regexp: Scan backwards for patterns ending in $

@sylvinus sylvinus mentioned this issue Apr 10, 2019
Open
@matloob matloob mentioned this issue Jul 1, 2020
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
help wanted NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
4 participants
@sylvinus @ianlancetaylor @odeke-em @gopherbot