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

Timeline