How Three Bytes Can Narrow a Repository
In microsoft/tgrep, the useful question is not whether a file contains an entire search pattern in a form the index understands. It is whether the file contains small, necessary fragments that many different searches can reuse. This chapter follows that idea from overlapping three-byte windows to per-file postings and compact masks, so readers can tell exactly how tgrep narrows work, what its summaries can reject, and why final matching still has the last word.
A file becomes a set of reusable fragments
A trigram is an overlapping window of three bytes. Take the text the cat. The first window is the; move one byte and the next is he ; continue moving one byte at a time and the windows eventually include ca and cat. The windows overlap because a search for a longer phrase is made from overlapping local facts, not from isolated three-character words.
Tgrep packs the three bytes into one 24-bit value inside a u32: the first byte occupies the high eight bits, the second the middle eight, and the third the low eight. That packing is important for two reasons. It is compact, and it is injective: different three-byte sequences produce different packed keys. There is no need to use a cryptographic digest to distinguish cat from car. The possible key space is large—about 16.7 million combinations—but the key itself still preserves the original three bytes without a collision at the packing step.
For each text file, tgrep extracts unique trigrams and associates them with the file’s identifier. If cat appears ten times in one file, the file needs one membership entry for that trigram, not ten identical file memberships. The result is an inverted relationship: instead of asking every file whether it contains cat, a query can ask the index which files are known to contain cat and begin with that smaller set.
The extractor does not allocate a giant table for every possible key for every file. It uses a sparse per-file map because ordinary source files contain only a small fraction of the possible 24-bit vocabulary. It walks the file’s overlapping windows, inserts a key the first time it sees it, and accumulates any additional information on later occurrences. This makes repetition cheap in the index representation while preserving the fact that the same fragment may occur in several locations or continuation contexts.
This is a necessary-condition index. Suppose a literal query is mutex_lock. Any exact occurrence of that literal contains the overlapping fragments mut, ute, tex, ex_, x_l, _lo, loc, and ock. A file that lacks even one required fragment cannot contain the literal. A file that contains all of them might contain them in different places, or in the wrong order, or separated by other text. The index can safely discard the first kind of file, but it cannot certify the second kind as a match.
That asymmetry is the basic contract of tgrep’s representation. The index is allowed to be incomplete as a description of why a file might match, as long as it never discards a file that really could match. It is not allowed to invent a narrower condition just because that condition would produce fewer candidates.
A posting therefore stores file membership rather than a full copy of the file. The path is resolved separately when the candidate is selected. This keeps one file path from being repeated inside every trigram list and lets a common search operation work with compact integer IDs before it needs to produce human-readable output. It also allows a single file to participate in many queries without storing a separate answer for each query.
Masks add cheap local evidence
Tgrep records more than a yes-or-no membership bit for a trigram. Each posting can carry two eight-bit summaries: loc_mask and next_mask.
loc_mask records the residue modulo eight of the byte offsets where the trigram occurs. If a trigram starts at an offset whose remainder after division by eight is three, bit three is set. Repeated occurrences may set several bits. Reducing every position to one of eight residues loses exact coordinates, but it creates a small summary that can be compared quickly. The source includes a rotate-and-AND adjacency check: if one literal fragment begins immediately before the next, their possible offset residues must line up after a one-bit rotation. Because the summary is periodic, it can admit false positives; it is useful only as a conservative filter.
next_mask summarizes the bytes that immediately follow each occurrence. It is an eight-bit Bloom-style filter: a following byte is mapped to one of eight bits, and that bit is set for the trigram’s posting. At query-planning time, tgrep can remember that a literal-derived trigram should be followed by a particular byte. During candidate selection, it checks the corresponding bit. If the bit is absent, that posting cannot represent the required continuation and can be rejected. If the bit is present, the byte may be there—or another byte may have mapped to the same bit—so the candidate must continue to full verification.
Consider a file that contains related fragments in separate words rather than the phrase the user requested. Some individual trigrams may appear, but the complete sequence of required fragments may not. If the required postings are missing, intersection removes the file early. If all the individual fragments happen to exist somewhere, the compact masks can sometimes remove more impossible arrangements, but they still do not preserve enough exact position information to settle the question in every case. The full matcher must inspect the surviving file.
The distinction between those two outcomes matters. A compact mask is valuable because it can cheaply eliminate some impossible candidates, not because it replaces the regex engine. A Bloom-style summary deliberately accepts collisions in its small bit space. The safe direction is always “reject only when the summary proves incompatibility.” Surviving candidates are read and matched against the actual pattern.
The masks also give tgrep a way to improve selectivity without storing a full position list for every trigram. A plain posting answers “this file has seen the fragment.” A masked posting can sometimes answer a stronger local question: “this file has seen the fragment in a compatible continuation context.” The storage increase is small because the two summaries add only two bytes to the file identifier in an on-disk posting. The trade is precision for compactness: the masks reduce work but do not carry enough information to explain every occurrence exactly.
The diagram shows why the same representation can be reused across queries. File content is converted into keys and summaries once. A later literal is converted into compatible keys, and posting lists are intersected. The output is only a candidate set; tgrep still reads those files and evaluates the full requested semantics.
Case-insensitive search without a second full copy
Case-insensitive lookup creates a representation problem. If the file contains AlertSchema but the query is written as alertschema, an index containing only the original-case trigrams would not find the file by looking for the lowercase keys. Tgrep addresses this by recording observations from both the original bytes and their ASCII-lowercased form.
The implementation’s important memory choice is how it creates those observations. A simple approach would make a complete lowercase copy of the file, extract the original trigrams, extract the lowercase trigrams in a second pass, and merge the results. Tgrep instead folds the lowercase calculation into the same window traversal. For each three-byte window, it first forms the original key. If the lowercase form differs, it also forms the lowered key and merges the masks into the corresponding entry. When a window is already lowercase, the two keys are the same and the second pass’s work collapses into an additional mask update rather than another full walk.
For example, a window from Foo contributes the original key for Foo and the lowercase key for foo. A window such as ell inside Hello can be present in both observations, so its location and continuation summaries are combined rather than treated as two unrelated facts. This preserves the offsets at which the source text supplied evidence while allowing a lowercase query to find content written with uppercase letters.
The following byte matters too. The next_mask for a lowercase observation must include the lowercase version of the byte that follows the window. Otherwise a case-insensitive literal could find the right trigram but be rejected because its continuation was recorded only with the original capitalization. Tgrep merges that continuation evidence at the same time as the key.
This is an example of the broader design theme: the index stores just enough generalized evidence to support reuse, while the exact matcher handles the user’s actual semantics. Case-insensitive lookup broadens the stored vocabulary, but it does not make the masks an authoritative case-folding engine. The final match still uses the requested matcher and its case settings.
Why not every file contributes useful trigrams
The representation has clear limits. A file shorter than three bytes cannot produce a trigram. A query shorter than three bytes cannot produce one either. A wildcard-only expression or a pattern whose fixed content is optional may have no fragment that must occur. In those cases, pretending that an empty set of required trigrams means “no files match” would be wrong. Tgrep treats the absence of safe fragments as a signal to broaden the search, often by considering all eligible files.
Binary handling creates a second boundary. The walker can reject common binary extensions before content indexing. For files that reach the content-reading stage, tgrep checks the first 8 KiB for a NUL byte. A binary file does not become a normal text posting merely because some bytes around it resemble source code. It may remain visible to filename listing or be handled specially when the user explicitly asks for binary content, but it is not allowed to pollute the ordinary text index.
Encoding has a related consequence. The trigram keys describe the bytes after tgrep’s indexing decoder has produced searchable text. If a later query asks for a different encoding, the file may turn into different searchable bytes. Reusing the old keys could then exclude a real result, so the indexed path is not used for that request. The index is tied not only to a path, but to the way the path’s content was interpreted when the evidence was created.
The same principle explains why a candidate set cannot be the final answer. A file may contain all the trigrams for mutex_lock but have mutex and clock in separate locations. The posting intersection can leave that file in the candidate set. The full regex matcher then checks order, adjacency, boundaries, repetition, and any other semantics that the compact summaries did not encode. If the matcher rejects it, tgrep reports nothing from that file.
Tgrep’s three-byte vocabulary is powerful precisely because it is modest. It does not attempt to predict every behavior of a regular expression from a compact index. It records a reusable, necessary signal; it applies cheap filters that can only remove impossible candidates; and it hands the survivors back to exact matching. The next question is how tgrep combines those small signals when the user’s pattern is itself more complicated than a literal.