From Regular Expression to Candidate Set
The trigram representation gives microsoft/tgrep reusable evidence about file content, but users do not usually search for a single isolated fragment. They search with regular expressions, alternatives, optional pieces, and sometimes richer PCRE-style features. This chapter explains how tgrep translates those patterns into safe combinations of trigram lookups, when it deliberately gives up pruning, and why the full matcher must verify every candidate that survives.
A pattern becomes a set operation
A regular expression describes a language: the collection of strings it can match. Tgrep does not try to encode that entire language in its trigram index. Instead, it asks a narrower question: which pieces must be present in every string the expression could match?
For a literal such as mutex_lock, every match contains the same overlapping three-byte fragments. The planner converts those fragments into an AND plan. In set terms, each trigram produces a set of file IDs, and the result is their intersection. A file remains a candidate only if it appears in every required posting list.
The planner starts with the shortest posting list. A rare trigram may occur in a handful of files, while a common trigram may occur in most of the repository. Intersecting the rare list first reduces the amount of work needed for later comparisons. Tgrep sorts posting lists by length, intersects sorted file IDs, and stops early if the candidate set becomes empty. This is a small algorithmic choice with a clear causal effect: fewer intermediate IDs mean fewer comparisons and fewer files to verify.
The intersection is still a filter, not a final answer. The trigrams may occur in different parts of the same file. The compact masks from the previous chapter can reject some incompatible continuations, but the exact regex engine must still read the candidate and check order, adjacency, boundaries, and every other part of the pattern.
Alternation changes the operation. For foo|bar, a match needs the fragments for foo or the fragments for bar. The planner creates an OR plan and unions the candidate sets. It must do this for every pattern supplied by the user, not only the first one. If a caller supplies two expressions through -e or -f, a file matching only the second expression is still a valid result. Building the plan from only the first expression would make the index appear selective by silently losing real matches.
Tgrep merges sorted ID lists and removes duplicates when it performs a union. That matters when one file contains both alternatives: it should be verified once, not once for each branch. The set operations are therefore not just an optimization detail. They are the structure that keeps the index’s view of alternatives aligned with the user’s request.
A concatenation can contain both fixed and variable parts. In an expression such as class [A-Za-z]+ Schema, the fixed literal runs still provide useful fragments, while the character class and repetition do not provide one exact sequence by themselves. Tgrep can collect the mandatory literal evidence it can identify and leave the variable part to final matching. It does not have to understand every possible string in the expression to obtain a safe narrowing signal; it only has to avoid requiring something that a real match does not require.
The planner derives continuation information from the parsed literal that produced each trigram, rather than treating every visible character in the raw pattern as a byte in the matched text. That distinction matters when a pattern uses escapes or other syntax whose spelling differs from the text it can match. If the same trigram appears in separate literal runs with different possible following bytes, tgrep avoids keeping one overly specific continuation requirement. Losing that extra filter may leave more candidates, but retaining it could discard a real match. Conservative planning often means accepting a little more verification work to preserve the correct candidate set.
When “no clue” means search broadly
The most important planner result is MatchAll. It does not mean that every file matches. It means that the index has no safe trigram condition with which to narrow the eligible corpus.
A pattern shorter than three bytes cannot produce a trigram. A wildcard such as .* can match without requiring any fixed bytes. An optional fragment can disappear from a match, so treating it as mandatory would risk discarding a true result. A character-class-only pattern may also have no fixed three-byte sequence. In each case, an empty candidate list would be a serious semantic error: it would confuse “the index found no necessary evidence” with “the regex has no matches.” Tgrep instead returns the broad plan and lets the caller consider all eligible files.
The same rule applies to an alternation with one unrestricted branch. Imagine a multi-pattern request containing a distinctive word and a one-character expression. The distinctive word could narrow its own branch, but the one-character expression can match in places that provide no three-byte requirement. The union must include every possible file for that branch, so the whole plan becomes MatchAll. Dropping the difficult branch would make the result fast and incomplete, which is the wrong trade.
This conservative choice is especially important for a negative request. Inverted matching asks for lines that do not match the expression. A positive trigram index is good at finding files that contain evidence of the expression, which is almost the opposite of the population an inverted search must inspect. A file with no matching trigram may be exactly the file the user wants. Tgrep therefore does not reuse positive pruning as if it were a safe negative index; it broadens the candidate population and lets the line-level matcher decide.
The same broad behavior can be required by options that change the searchable corpus. Passthrough output needs non-matching lines as well. A non-default encoding can turn the file into different searchable bytes from those used to build the index. Tgrep uses all eligible files or bypasses the indexed path for such requests instead of pretending that a positive-content index can answer a negative or differently decoded question.
Some options force the same broad behavior even when the pattern itself contains useful literals. A query that asks to reinclude ignored files, search binary content, or use traversal rules different from the index’s rules cannot safely use postings built for the original corpus. A plan can fail to help without failing the search. Tgrep’s local search path can scan the files directly, and a client that contacts a server while its index is not ready can fall back to a local index or filesystem scan. The system gives up an optimization, not correctness.
Safe widening for richer regex
The standard regex parser used by tgrep does not accept every construct supported by the PCRE-style engine. That creates a choice for a pattern such as (?<!//)ExchangePrincipal: either abandon index pruning entirely, or find a safe approximation that preserves the original pattern’s necessary content.
Tgrep’s relaxation rule is deliberately one-way. It may remove a zero-width lookaround, because removing a condition makes the accepted language wider. It may turn an atomic group into an ordinary non-capturing group, because restoring backtracking paths also widens what the approximation can accept. The relaxed pattern may identify ExchangePrincipal as required even though it no longer expresses the “not preceded by //” condition.
Why does widening help? Let the original pattern accept a set of strings called L, and let the relaxed pattern accept L′. The safe relationship is L is a subset of L′. Every string matched by the original is still matched by the relaxed form, though the relaxed form may match additional strings. A trigram required by the relaxed form is therefore required by every original match too. It may leave extra files in the candidate set, but it cannot remove a file that the original could match.
Narrowing would be unsafe. If a rewrite accidentally added a constraint, the index could omit a genuine hit before the real matcher ever saw it. Tgrep therefore refuses to guess when it cannot establish the widening direction. Backreferences, conditionals, \K, \G, and ambiguous possessive-quantifier cases return no relaxation. The result is a full scan rather than an optimistic candidate filter.
The real PCRE-style matcher remains in charge even when relaxation succeeds. The relaxed form is useful for finding a smaller set of files; it is not the expression whose results the user requested. In the matching layer, a linear-time prefilter can rule out a file when the relaxed expression fails. A successful prefilter only says “do not discard this file.” Tgrep then runs the fancy matcher, which checks the original lookaround, backreference, or other advanced condition.
This explains a subtle but important distinction between the planner and the matcher. The planner reasons about what must be present. The matcher reasons about what actually satisfies the request. The first can be intentionally broader than the second, but never narrower.
The sequence shows the ownership boundary. The planner decides how much of the corpus can be eliminated safely. The index returns IDs, not final text results. The full matcher decides which candidates satisfy the original expression, or searches the entire eligible set when planning cannot narrow it.
Why the parser’s representation matters
Tgrep builds plans from the parser’s intermediate representation rather than by searching the raw pattern text for convenient-looking words. This matters because the raw spelling of a regex is not always the text that it matches. Escapes, character classes, case-insensitive settings, repetition, anchors, and grouping can change the relationship between pattern characters and matched bytes.
The planner collects literal runs from concatenations and derives expected continuation bytes from the parsed literal. It can then attach mask checks to the same fragment that supports them. If the same trigram appears in multiple contexts with different expected following bytes, tgrep avoids retaining a misleading single continuation constraint. The goal is not to maximize filtering at any cost; it is to keep each filter justified by the parsed structure that produced it.
The same discipline prevents an optional fragment from becoming an accidental requirement. In a pattern where a fixed word appears inside a branch that may be skipped, the word is evidence for that branch, not for every possible match. In a pattern with fixed runs around a variable expression, the fixed bytes can still narrow files, but they do not tell the index where the final match begins or ends. The planner preserves those distinctions by following the parsed structure instead of treating syntax as a bag of visible words.
Alternation and repetition also show why structural parsing beats textual guessing. A literal inside an optional branch is not automatically required for the whole expression. A fixed run on either side of a variable expression can remain useful, but the planner must preserve the possibility that the variable expression changes the matched span. Treating syntax as a bag of visible words would produce false confidence about what every match must contain.
The same care appears in multiple-pattern handling. A command may use fixed strings that contain regex punctuation, or regular expressions that use alternation. Tgrep builds the actual matcher from the complete request and builds the candidate plan from the same collection of patterns. The two paths can use different representations, but they must describe the same user request. Otherwise a server-backed search and a direct search could disagree depending only on whether a daemon happened to be running.
The boundary that makes the optimization trustworthy
A useful way to evaluate tgrep’s query planner is to ask what happens in three cases. If the pattern has strong mandatory fragments, tgrep intersects or unions posting lists and verifies a reduced candidate set. If the pattern has some fixed evidence but also richer structure, tgrep may use a widened plan or a conservative prefilter, then verify with the original matcher. If no safe evidence exists—or the requested options change the searchable corpus—it broadens the search or bypasses the index.
Only the first stage is responsible for speed. The second protects the speed path from false positives, and the third protects the user from false negatives. That arrangement means a query can be slower for a principled reason: the system refuses to convert an uncertain interpretation into a missing result.
The planner therefore turns the three-byte vocabulary into something more expressive without pretending that the index understands regular expressions completely. AND and OR encode necessary relationships. MatchAll marks the absence of a safe narrowing condition. Relaxation recovers useful evidence only when it widens the language. Full matching remains the authority. With that contract in place, the next engineering question is physical: how can tgrep store and build the posting data so these lookups stay affordable at repository scale?