Regex to mandatory-trigram query (Russ Cox / Google Code Search).

Turns a regex into a boolean trigram query that every matching document must satisfy, so intersecting it over the index yields a superset of matches that the real regex engine then confirms. The query is only ever a NECESSARY condition: wherever the analysis is unsure it emits all (no constraint), which is always sound and just widens the candidate set.

A small recursive-descent parser builds an AST for a practical subset (adjacent literal bytes coalesced into one run, so abcdef yields every internal trigram). The analysis assigns each node a query: concatenation ANDs, alternation ORs, */?/./char-class/anchors contribute all, + takes its child's query, and a literal run ANDs its trigrams. This deliberately stops short of the full Cox exact/prefix/suffix cross-product (boundary trigrams spanning alternations); literal-run coalescing already covers the common case.