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: crash in new backtrack engine #10319

Closed
rsc opened this issue Apr 2, 2015 · 9 comments
Closed

regexp: crash in new backtrack engine #10319

rsc opened this issue Apr 2, 2015 · 9 comments
Milestone

Comments

@rsc
Copy link
Contributor

rsc commented Apr 2, 2015

panic: runtime error: index out of range [recovered]
    panic: runtime error: index out of range

goroutine 9 [running]:
regexp.(*machine).backtrack(0xc2085c4ea0, 0xac7ce0, 0xc2085c4f78, 0x0, 0x2b26, 0x0, 0x4b2fc0)
    /Users/rsc/g/go/src/regexp/backtrack.go:343 +0x394
regexp.(*Regexp).doExecute(0xc208085040, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc208a1e000, 0x2b26, 0x0, 0x0, ...)
    /Users/rsc/g/go/src/regexp/exec.go:449 +0x413
regexp.(*Regexp).MatchString(0xc208085040, 0xc208a1e000, 0x2b26, 0x3e00)
    /Users/rsc/g/go/src/regexp/regexp.go:406 +0xc8
main.(*builder).processOutput(0xc20846afc0, 0xc2086a0000, 0x2b26, 0x3e00, 0x0, 0x0)
    /Users/rsc/g/go/src/cmd/go/build.go:1426 +0x146
main.(*builder).build(0xc20846afc0, 0xc208552c30, 0x0, 0x0)
    /Users/rsc/g/go/src/cmd/go/build.go:972 +0x25f6
main.(*builder).do.func1(0xc208552c30)
    /Users/rsc/g/go/src/cmd/go/build.go:737 +0x3a8
main.(*builder).do.func2(0xc2087b2940, 0xc20846afc0, 0xc2087b2920)
    /Users/rsc/g/go/src/cmd/go/build.go:794 +0x155
created by main.(*builder).do
    /Users/rsc/g/go/src/cmd/go/build.go:800 +0x49f

The line in question is

b.cap[0] = pos

I extracted the specific regexp and input that caused this but in the obvious 1-line program there is no crash. This suggests there is something bad in the caching of machines. I don't have a simple program to provoke this, but maybe that's enough information anyway.

@michaelmatloob
Copy link
Contributor

What are the regexp and input that caused this?

@rsc
Copy link
Contributor Author

rsc commented Apr 2, 2015

I will email them to you but it shouldn't matter. It's b.cap[0] being written to. That's the overall match. And as I said, the obvious 1-line use of them doesn't crash.

@michaelmatloob
Copy link
Contributor

Ok. How can I reproduce the panic? What program was the example contained in?

@rsc
Copy link
Contributor Author

rsc commented Apr 3, 2015

Instead of trying to reproduce it, let's look at what's already been reported. b.cap[0] = pos is being executed and failing because len(b.cap) is apparently 0. Why is it okay to write to b.cap[0] on that line? It looks to me like in the stack trace the argument reqcap passed to backtrack is 0.

@mattyb
Copy link
Contributor

mattyb commented Apr 5, 2015

This may duplicate #10316. A possible patch is here: https://go-review.googlesource.com/#/c/8473/1/src/regexp/exec.go

@michaelmatloob
Copy link
Contributor

I think these are separate issues.

When porting the backtracking code, I made the assumption that len(m.matchcap) is always >= 2. Then b.cap would be initialized (via the call to b.reset) to have at least length len(m.matchcap), so accesses to b.cap[0] and b.cap[1] would always be valid. And that assumption is true whenever a machine only runs the backtracker because when a machine is initalized in progMachine, its minimum length is set to 2. However, when the standard matcher is used, m.matchcap is resliced (in m.init) to ncap which may have length less than 2. So if the backtracker is run after the standard matcher on the same machine and no captures are requested the assumption won't hold.

So the backtracking code can either check for reqcap when setting b.cap[0] or b.cap[1], or initalize b.cap to have length at least 2.

@rsc
Copy link
Contributor Author

rsc commented Apr 6, 2015

Please send a CL fixing this. I would check reqcap. There's no point filling out b.cap[0] if it's not needed.

@mattyb
Copy link
Contributor

mattyb commented Apr 9, 2015

Sorry, it seems I tagged the wrong issue in a513088. That closed #10316, but @michaelmatloob points out this is a different issue

@mikioh mikioh reopened this Apr 9, 2015
@josharian
Copy link
Contributor

Here's a reproducer using tip: http://play.golang.org/p/xxYClfmmjK. Hope that helps. Sorry about the size and noise in it. Too distracted by other things to minimize at the moment.

@golang golang locked and limited conversation to collaborators Jun 25, 2016
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

6 participants