Regex and Structural Search

Beyond Simple Text Matching

Trigrams handle exact substring searches efficiently. But developers rarely search for exact strings. They search for patterns: "Find all functions that return an error without logging it" or "Find every place we construct an HTTP client without setting a timeout."

Two technologies extend trigram search to handle these cases: regex acceleration and structural search.

Regex Acceleration

Regular expressions are powerful but expensive. Running a regex like [a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,} (an email pattern) against every file in a 1.6TB codebase would take hours.

Trigram indexes can accelerate regex queries by extracting required literal substrings from the regex and using them to pre-filter. The regex engine analyzes the pattern and identifies trigrams that must appear in any matching string. For example, the email regex above requires the literal character @. The trigram index can immediately eliminate all files that don't contain @, reducing the candidate set dramatically before the regex engine runs a single comparison.

This technique — called regex-to-trigram rewriting — is implemented in Zoekt and Google's internal Code Search (described in the paper "Regular Expression Matching with a Trigram Index"). Not all regexes can be accelerated this way (patterns like .* provide no useful trigrams), but most developer search patterns contain enough literal characters to benefit significantly.

Structural Search (Comby)

Text search and regex treat source code as a flat string. They don't understand that ( must be matched by ), or that a string literal ends at the closing quote. This causes two problems:

1. False positives: Searching for fmt.Sprintf( matches commented-out code, string literals containing that text, and test mocks — not just real call sites.
2. Inability to express code-level patterns: You cannot write a regex that matches "a function call with exactly two arguments where the first is a string literal starting with Error:".

Structural search solves this by parsing code into its syntactic structure before matching. Sourcegraph integrates Comby, a structural search tool that understands balanced delimiters and code-level constructs.

A Comby pattern looks like this:

fmt.Sprintf("Error: %v", :[args])

The :[args] placeholder matches any expression in that argument position, including multi-line expressions with nested parentheses — something no regex can reliably handle. This pattern will match:

fmt.Sprintf("Error: %v", err)
fmt.Sprintf("Error: %v", fmt.Errorf("wrapped: %w", err))

But it will not match:

// fmt.Sprintf("Error: %v", err)   ← commented out
s := "fmt.Sprintf(\"Error: %v\", x)"  ← inside a string literal

Large-Scale Refactoring

The practical payoff of structural search is safe, automated refactoring at scale. Consider migrating from a deprecated API:

# Find all calls to the old API
http.Get(:[url])

# Replace with the new API
http.NewRequest("GET", :[url], nil)

Running this pattern across 5,000 repositories finds every call site, regardless of formatting differences, and generates a diff that can be applied automatically. A text-based find-and-replace would miss cases where the arguments span multiple lines or where whitespace differs between teams.

Key Point: Structural search understands code syntax, not just text. This makes it the correct tool for large-scale refactoring, where false positives from text search would require manual review of thousands of results — eliminating the efficiency gain entirely.