re.MatchString Benchmark cost too much time

[tjbrains]

the benchmark cost 116.923s to finish, there is maybe a issue here:

func BenchmarkMatchStringCache_WithoutCache_coregex(b *testing.B) {
	runtime.GOMAXPROCS(4)

	var data = strings.Repeat("Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/96.0.4664.110 Safari/537.36", 8)
	var re = coregex.MustCompile(`(?iU)\b(eval|system|exec|execute|passthru|shell_exec|phpinfo)\b`)

	b.ReportAllocs()
	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			_ = re.MatchString(data)
		}
	})
}

result:

goos: darwin
goarch: arm64
pkg: [MY REPOSITORY]/internal/waf/utils
cpu: Apple M2 Max
BenchmarkMatchStringCache_WithoutCache_coregex-12            100        1148587620 ns/op        1737521223 B/op     1445 allocs/op
testing: BenchmarkMatchStringCache_WithoutCache_coregex-12 left GOMAXPROCS set to 4
PASS
ok      github.com/[MY REPOSITORY]/internal/waf/utils        116.923s

[tjbrains]

and with go stdlib regexp result:

goos: darwin
goarch: arm64
pkg: [MY REPOSITORY]/internal/waf/utils
cpu: Apple M2 Max
BenchmarkMatchStringCache_WithoutCache_regexp
testing: BenchmarkMatchStringCache_WithoutCache_regexp-12 left GOMAXPROCS set to 4
BenchmarkMatchStringCache_WithoutCache_regexp-12    	   91040	     12997 ns/op	       0 B/op	       0 allocs/op
PASS

[kolkov]

Thank you for the report! This is a confirmed critical performance issue.

Root Cause

The problem is in our literal extractor — it currently rejects ALL case-insensitive patterns entirely (a blanket guard added for #87). Without extracted literals, the meta-engine has no prefilter candidates and falls back to lazy DFA, which suffers from state space explosion on (?i) patterns (181 NFA states → massive DFA cache thrashing).

For comparison, Rust's regex crate handles this pattern by:

1. Expanding case-insensitive literals into all folding variants (eval → EVAL, EVAl, EVaL, ... eval = 16 variants)
2. Trimming to 3-byte prefixes (60 total)
3. Using Teddy SIMD prefilter to scan — finds 0 candidates in your input → returns immediately in ~263ns

Our engine should do the same but currently skips step 1, so Teddy is never engaged.

Fix Plan

1. Literal extractor: Support case-folding expansion for (?i) alternation literals (like Rust does)
2. Strategy: Route expanded literals to Teddy/Aho-Corasick prefilter
3. Safety net: Add fallback from DFA to PikeVM for large NFAs without prefilter — prevents cache thrashing even when literal extraction isn't possible

Workaround (until fix is released)

You can manually expand the case variations and drop (?i):

// Instead of:
re := coregex.MustCompile(`(?iU)\b(eval|system|exec|execute|passthru|shell_exec|phpinfo)\b`)

// Use case-sensitive with explicit variations:
re := coregex.MustCompile(`\b(?i:eval|system|exec|execute|passthru|shell_exec|phpinfo)\b`)

If that doesn't help, the fastest workaround is to list lowercase only (if your input is predictable):

re := coregex.MustCompile(`\b(eval|system|exec|execute|passthru|shell_exec|phpinfo)\b`)

This routes to Teddy strategy (~200ns/op) since literals are extracted correctly without (?i).

We'll prioritize the fix. Thank you for the detailed benchmark — the RunParallel with GOMAXPROCS(4) test is especially valuable as it exposes DFA cache contention under concurrency.