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

regexp: nested x{n} makes isOnePass take too long #7608

Closed
rui314 opened this issue Mar 22, 2014 · 4 comments
Closed

regexp: nested x{n} makes isOnePass take too long #7608

rui314 opened this issue Mar 22, 2014 · 4 comments
Milestone

Comments

@rui314
Copy link
Member

rui314 commented Mar 22, 2014

What does 'go version' print?
go version devel +82edfcdee1bc Thu Mar 06 13:15:09 2014 +1100 linux/amd64

What steps reproduce the problem?
If you run `^(?:x{1,1000}){1,1000}$` on "xxxxxxxx ...(5000 times)... y",
FindString does not return. If the repetition is short, it will return immediately.
http://play.golang.org/p/uh55Y8ajc6
@bradfitz
Copy link
Contributor

Comment 1:

Labels changed: added release-go1.3maybe, repo-main.

Owner changed to @rsc.

Status changed to Accepted.

@rsc
Copy link
Contributor

rsc commented Mar 24, 2014

Comment 2:

It's not exponential. You can't prove an exponential run time with a single data point.
It's linear in the size of the repetition with a very large constant (derived from the
size of the regexp, and the size of that regexp is ~ 1 million).
That said, IsOnePass - added during the 1.3 cycle - is taking far too long to analyze
the regexp and is blowing out the stack. That needs to be fixed for 1.3.
package main
import (
    "regexp"
    "strings"
    "time"
    "fmt"
)
func main() {
    re := regexp.MustCompile(`^(?:x{1,1000}){1,1000}$`)
    println("compiled")
    for i := 5; i < 5000; i *= 2 {
        s := strings.Repeat("x", i) + "y"
        t := time.Now()
        re.FindString(s)
        fmt.Println(i, time.Since(t))
    }
}

Labels changed: added release-go1.3, removed release-go1.3maybe.

@gopherbot
Copy link

Comment 4:

CL https://golang.org/cl/92290043 mentions this issue.

@robpike
Copy link
Contributor

robpike commented May 13, 2014

Comment 5:

This issue was closed by revision f54f790.

Status changed to Fixed.

@rsc rsc added this to the Go1.3 milestone Apr 14, 2015
@rsc rsc removed the release-go1.3 label Apr 14, 2015
@golang golang locked and limited conversation to collaborators Jun 25, 2016
@rsc rsc removed their assignment Jun 23, 2022
This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

5 participants