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

[rui314]

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]

Comment 1:

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

Owner changed to @rsc.

Status changed to Accepted.

[rsc]

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]

Comment 4:

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

[robpike]

Comment 5:

This issue was closed by revision f54f790.

Status changed to Fixed.