Preserve Unicode fold classes in extracted regexp filters
perfloop-oss/zoekt · Uncatalogued correctness
https://perfloop.ai/t/oss/case_cazf4bdj19
Verdict
VERIFIED · settled 2026-11-13 · merged as sourcegraph/zoekt#1230
What happened: The check fails before this change and passes with it.
Hypothesis
Case-insensitive regexp filters can discard files that Go's regexp matches. The letters s and ſ, and the Greek letters σ and ς, compare equal under Unicode case folding but do not have identical lowercase forms. This failure occurs in the extracted filter, before fallback execution. Its frequency in consumer queries is unknown.
The literal branch at index/eval.go:628–633 creates a case-insensitive substring tree for folded literals and reports equivalence. newMatchTree returns that tree directly when isEq is true at index/matchtree.go:1030–1037. When equivalence is false, the extracted filter is still mandatory through noVisitMatchTree at 1052–1056. Candidate generation uses unicode.SimpleFold at index/bits.go:27–47, but verification compares a lowered pattern with unicode.ToLower of the subject in caseFoldingEqualsRunes at 63–95. Lowercasing does not implement all Unicode fold classes.
The first failed checkProperty(prop_w0zdttjk1x) run at c11c1cb52bdc4fde9a31a68ca9df182b3770cdd7 completed a finite nested grammar: 4400 patterns, 1833 token-generated subjects, two targets and two case settings. It performed 32260800 comparisons and found 167672 rejected positive matches in that constructed population. Those counts are not a production failure rate. Its returned replay file retains the reduced extraction witnesses sss on ssſ and σσσ on σσς, both case-insensitive. The latter pattern and subject have equal UTF-8 widths.
A second required checkProperty(prop_w0zdttjk1x) run failed directly on both stored replays, where extraction reports equivalent=true. It also reproduced file loss in all 16 deterministic ordinary-query configurations: the two Unicode examples, content or filename, line or chunk output, and case:no or an inline fold flag with case:yes. For example, case:no content:σσσ$ returns no file for σσς. The isolated default fallback accepted the sigma example in the same check; the extracted prefilter rejected it. RE2 was disabled. Thus retaining regexp execution alone does not remove this failure.
The smallest Case check is the stored command go test ./index -run '^TestPerfloopRegexpPrefilter(Conservative|UnicodeReplay)$' -count=1 -timeout=180s -v. The independent proof target is conservative filtering under Unicode fold classes, with ordinary Search returning the matching files and correct byte spans. The stored native replays check the complete subject span in both result formats when a file is returned. A Unicode-fold-class sweep is a useful next assurance check; the existing finite matrix is not an unbounded proof.
This is distinct from hyp_a1vxhkm6xv, whose recorded prefilter accepts its Kelvin-sign witness and whose repair addresses a fixed-byte-width prefix shortcut in grafana/regexp. The sigma replay here is rejected before that engine despite equal widths. It is also separate from hyp_34qjsa0xhf's repetition/alternation range selection and the already-landed ASCII comparison optimization. No query-language extension or ISA-specific implementation is required.
Current open upstream work was refreshed before publication. The actual implementation in https://github.com/sourcegraph/zoekt/pull/1224 changes word-boundary advancement. Draft https://github.com/sourcegraph/zoekt/pull/1223 and merged https://github.com/sourcegraph/zoekt/pull/1214 change compilation caching. None implements Unicode fold-class verification in extracted substring filters.
Change to test: Make case-insensitive substring verification preserve Unicode simple-fold equivalence and the matched subject's actual byte length. Establish that extracted filters remain conservative both when regexp execution is retained and when an equivalent tree replaces it.
Where it lives
perfloop-oss/zoekt · index/eval.go
Evidence
The check fails before this change and passes with it: `For sss/ssſ and σσσ/σσς, case-insensitive Search returns the matching file with the complete subject byte span for content and filename searches in line and chunk results, under case:no and inline folding with case:yes, in the single-repeat and leading-wildcard query forms that exercise equivalent extraction and retained regexp execution.`
The check fails before this change and passes with it: `For all unequal Unicode simple-fold rune pairs, candidate verification of an ab-prefixed pattern against an AB-prefixed subject succeeds without error and reports the subject's UTF-8 byte length; it rejects abcİ/abci in both directions.`
ASCII substring verification · 9 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
59.17 |
49.66 |
−16.5% (−9.76) |
−11.53 to −5.7 |
loss ≤ min(0, 0.05 × |baseline median|) |
PASSED |
Uppercase ASCII substring verification · 11 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
57.1 |
49.79 |
−12.8% (−7.33) |
−8.57 to −4.97 |
loss ≤ min(0, 0.05 × |baseline median|) |
PASSED |
Unicode substring verification · 12 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
138.7 |
133.9 |
−3.4% (−4.7) |
−10.1 to −3.6 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Uppercase Unicode candidate matching · 13 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
40.97 |
48.35 |
+7.45 |
−1.83 to +11 |
loss ≤ stated 0.35 × |baseline median| |
PASSED |
Rejected Greek substring candidates · 27 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
20.98 |
26.74 |
+28.4% (+5.96) |
+3.72 to +10.82 |
loss ≤ stated 0.6 × |baseline median| |
PASSED |
Rejected emoji substring candidates · 24 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
21.85 |
26.43 |
+22.6% (+4.93) |
+3.72 to +10.75 |
loss ≤ stated 0.6 × |baseline median| |
PASSED |
Nine-rune Greek candidate matching · 14 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
48.54 |
63.52 |
+29% (+14.07) |
+8.81 to +23.72 |
loss ≤ stated 0.75 × |baseline median| |
PASSED |
Nine-rune sigma candidate matching · 15 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
54.4 |
73.97 |
+37.9% (+20.62) |
+10.68 to +30.91 |
loss ≤ stated 0.8 × |baseline median| |
PASSED |
Three-rune Greek content Search · 192 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
5973 |
6045 |
+91 |
−59 to +284 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Three-rune Greek filename Search · 57 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
3465 |
3452 |
−21 |
−212 to +135 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Greek content Search across 128 lines · 16 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
87269 |
91308 |
+4646 |
−3512 to +14580 |
loss ≤ stated 0.2 × |baseline median| |
PASSED |
Rejected Greek content Search · 38 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
4893 |
4878 |
+6 |
−257 to +224 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Kelvin-suffix candidate rejection · 55 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
8.802 |
8.895 |
+0.042 |
−0.338 to +0.421 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Kelvin-suffix rejection after an ASCII prefix · 16 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
185.9 |
133.5 |
−27.7% (−51.5) |
−69.7 to −44.4 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Candidate rejection after a Greek alpha prefix · 16 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
1525 |
2225 |
+45.8% (+698) |
+660 to +760 |
loss ≤ stated 0.85 × |baseline median| |
PASSED |
Candidate rejection after a sigma prefix · 17 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
1707 |
2405 |
+40.2% (+686) |
+603 to +844 |
loss ≤ stated 1 × |baseline median| |
PASSED |
Three-rune Unicode candidate matching · 17 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
19.34 |
20.93 |
+1.54 |
−23 to +3.33 |
loss ≤ stated 0.5 × |baseline median| |
PASSED |
Three-rune ASCII candidate rejection · 17 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
9.054 |
11.07 |
+1.963 |
−0.32 to +4.17 |
loss ≤ stated 0.8 × |baseline median| |
PASSED |
Three-rune Unicode candidate rejection · 17 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
14.29 |
17.51 |
+3.21 |
−3.62 to +4.58 |
loss ≤ stated 0.8 × |baseline median| |
PASSED |
Three-rune Greek candidate matching · 17 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
38 |
53.71 |
+39.1% (+14.85) |
+13.04 to +19.81 |
loss ≤ stated 1 × |baseline median| |
PASSED |
Three-rune sigma candidate matching · 17 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
42.49 |
61.97 |
+46.1% (+19.59) |
+10.28 to +22.04 |
loss ≤ stated 1 × |baseline median| |
PASSED |
Rejected Latin-1 substring candidates · 17 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
19.41 |
22.64 |
+1.18 |
−2.95 to +5.97 |
loss ≤ stated 0.5 × |baseline median| |
PASSED |