barrel_ngram_regex (barrel_ngram v0.9.0)
View SourceRegex to mandatory-trigram query (Russ Cox / Google Code Search), plus width/anchor analysis for the positional planner.
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.
analyze/1 is the strict entry point: any construct outside an explicitly-supported list (lookarounds, backreferences, named groups, \x escapes, \Q...\E, conditionals, a scoped/mid-pattern inline modifier) makes the whole pattern unsupported rather than being silently mis-parsed as literal text. A leading (?i)/(?s)/(?m) is the one inline-modifier form understood.
Summary
Functions
Full analysis: AST, trigram query, and width/anchor/leading-modifier info. See the moduledoc for exactly what makes a pattern unsupported.
Literal runs a positional planner may anchor a window on: only a pure AND-chain (a {cat, Nodes} with no {alt, _} child, or a bare {lit, _}), each paired with its own PrefixMax/SuffixMax (the upper-bound width of everything before/after it in the chain, unbounded if that side has an unbounded quantifier). ineligible for anything else, including a {lit, _} merely sitting next to an {alt, _} -- a real match could come from a different branch, so the whole chain is rejected rather than reasoning about which literals would still be safe.
The mandatory-trigram query for a regex -- always sound (never a guessed-at partial parse of an unsupported construct); all when the pattern is unsupported or carries no usable trigram constraint.
Types
-type literal_run() :: #{bytes := binary(), prefix_max := non_neg_integer() | unbounded, suffix_max := non_neg_integer() | unbounded}.
-type query() :: {'and', [query()]} | {'or', [query()]} | {gram, barrel_ngram_selector:gram()} | all | none.
-type width() :: {fixed, non_neg_integer()} | {bounded, non_neg_integer(), non_neg_integer() | infinity} | unbounded.
Functions
-spec analyze(binary()) -> {ok, term(), query(), width_info()} | unsupported.
Full analysis: AST, trigram query, and width/anchor/leading-modifier info. See the moduledoc for exactly what makes a pattern unsupported.
-spec literal_runs(term()) -> [literal_run()] | ineligible.
Literal runs a positional planner may anchor a window on: only a pure AND-chain (a {cat, Nodes} with no {alt, _} child, or a bare {lit, _}), each paired with its own PrefixMax/SuffixMax (the upper-bound width of everything before/after it in the chain, unbounded if that side has an unbounded quantifier). ineligible for anything else, including a {lit, _} merely sitting next to an {alt, _} -- a real match could come from a different branch, so the whole chain is rejected rather than reasoning about which literals would still be safe.
Parse to the internal AST (exported for tests). Raises on any construct analyze/1 treats as unsupported -- callers wanting the fail-closed behavior should use analyze/1, not this directly.
The mandatory-trigram query for a regex -- always sound (never a guessed-at partial parse of an unsupported construct); all when the pattern is unsupported or carries no usable trigram constraint.