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
diff --git a/src/pkg/regexp/all_test.go b/src/pkg/regexp/all_test.go
index a84c641..301a1df 100644
--- a/src/pkg/regexp/all_test.go
+++ b/src/pkg/regexp/all_test.go
@@ -473,6 +473,11 @@
}
}
+// This ran out of stack before issue 7608 was fixed.
+func TestOnePassCutoff(t *testing.T) {
+ MustCompile(`^(?:x{1,1000}){1,1000}$`)
+}
+
func BenchmarkLiteral(b *testing.B) {
x := strings.Repeat("x", 50) + "y"
b.StopTimer()
@@ -588,6 +593,7 @@
re.Match(x)
}
}
+
func BenchmarkNotOnePassShortA(b *testing.B) {
b.StopTimer()
x := []byte("abcddddddeeeededd")
@@ -597,6 +603,7 @@
re.Match(x)
}
}
+
func BenchmarkOnePassShortB(b *testing.B) {
b.StopTimer()
x := []byte("abcddddddeeeededd")
@@ -606,6 +613,7 @@
re.Match(x)
}
}
+
func BenchmarkNotOnePassShortB(b *testing.B) {
b.StopTimer()
x := []byte("abcddddddeeeededd")
@@ -615,6 +623,7 @@
re.Match(x)
}
}
+
func BenchmarkOnePassLongPrefix(b *testing.B) {
b.StopTimer()
x := []byte("abcdefghijklmnopqrstuvwxyz")
@@ -624,6 +633,7 @@
re.Match(x)
}
}
+
func BenchmarkOnePassLongNotPrefix(b *testing.B) {
b.StopTimer()
x := []byte("abcdefghijklmnopqrstuvwxyz")
