]> Cypherpunks repositories - gostls13.git/commit
regexp/syntax: don't waste time checking for one pass algorithm
authorRob Pike <r@golang.org>
Tue, 13 May 2014 19:17:49 +0000 (12:17 -0700)
committerRob Pike <r@golang.org>
Tue, 13 May 2014 19:17:49 +0000 (12:17 -0700)
commitf54f790a77274b132b64587f6cf1baea42d60709
tree44010bd460b6d3a93e0936d2350d2a7b61502bfb
parent5bc1cef869b0c6caea2d680010908cf6871c6c24
regexp/syntax: don't waste time checking for one pass algorithm
The code recurs very deeply in cases like (?:x{1,1000}){1,1000}
Since if much time is spent checking whether one pass is possible, it's not
worth doing at all, a simple fix is proposed: Stop if the check takes too long.
To do this, we simply avoid machines with >1000 instructions.

Benchmarks show a percent or less change either way, effectively zero.

Fixes #7608.

LGTM=rsc
R=rsc
CC=golang-codereviews
https://golang.org/cl/92290043
src/pkg/regexp/all_test.go
src/pkg/regexp/syntax/prog.go