Skip to content

ARCHITECTURE.md

Latest commit

 

History

History
171 lines (135 loc) · 7.78 KB

ARCHITECTURE.md

File metadata and controls

171 lines (135 loc) · 7.78 KB
Raw

How grix works

grix answers grep-style queries in milliseconds by consulting a trigram index instead of reading every file. This document explains the moving parts. It assumes nothing beyond knowing what a regular expression is.

The big picture

grix index            grix <pattern>
     │                      │
     ▼                      ▼
┌─────────┐   ┌──────────────────────────┐
│ walker   │   │ planner: regex → trigram │
│ extract  │   │ query ("abc" AND "bcd")  │
│ postings │   └──────────┬───────────────┘
└────┬─────┘              ▼
     ▼            ┌──────────────┐    ┌─────────────────┐
  index file ───▶ │ posting list │ ─▶ │ confirming scan │ ─▶ results
  (mmap'd)        │ intersection │    │ (real regex, on │
                  └──────────────┘    │ current files)  │
                                      └─────────────────┘

Two phases at query time:

  1. Planning narrows the candidate set using the index (microseconds).
  2. Confirming scan runs the actual regex over the candidates' current content (milliseconds, parallel).

Because the scan always reads live files, grix never reports a line that is not really there. A stale index can only miss very recent edits — run grix index (incremental, typically ~1s) to catch up.

Trigrams

A trigram is any 3 consecutive bytes. hello contains hel, ell, llo. The index maps every trigram that occurs in the tree to the sorted list of files containing it (a posting list), delta- and varint-encoded.

If you search for hello, a matching file must contain all three trigrams. Intersecting three posting lists is enormously cheaper than reading every file: that is the entire trick, and it is the same one behind Google Code Search (2006).

The planner: regex → trigram query

The interesting part is doing this for arbitrary regexes, not just literals. src/plan.rs is a clean-room Rust implementation of the algorithm Russ Cox described in Regular Expression Matching with a Trigram Index, adapted to operate on regex-syntax's HIR.

For every regex node it computes:

field meaning
can_empty can this subexpression match the empty string?
exact the complete set of strings it can match (if small enough)
prefix possible match prefixes (when exact overflows)
suffix possible match suffixes
query trigrams any match must contain (AND/OR tree)

Composition rules do the work. Sketches:

  • Concat: exact(xy) = exact(x) × exact(y) (bounded cross product). When the product overflows, the boundary suffix(x) × prefix(y) still yields guaranteed substrings — their trigrams are ANDed into the query.
  • Alternation: union of sets, OR of queries.
  • x+: at least one copy, so x's trigrams still hold; exact strings demote to prefixes/suffixes (a match may continue).
  • x*, x?: may match empty — contributes nothing (degrades toward match-all rather than risk a wrong constraint).
  • Classes: [ab] enumerates into the exact set; big classes (\w) become "any char".

Examples (grix --explain shows these):

Abcdef        →  "Abc" "bcd" "cde" "def"
abc.*def      →  "abc" "def"
abc|def       →  ("abc"|"def")
(abc)?def     →  "def"
a[0-9]z       →  ("a0z"|"a1z"|…|"a9z")
\w+           →  ALL          (scan everything — still correct)

The single invariant the planner must uphold: it may only require trigrams guaranteed to appear in every match. Whenever the analysis cannot guarantee anything it degrades to ALL, which means "scan every file" — slower, never wrong. An over-constraining planner bug would silently hide results, which is why the test suite's core property test asserts search-with-index ≡ full-scan across every pattern shape the planner handles, and why query minimization (subsumption pruning: in an OR, a branch implied by a weaker branch is dropped) is implemented as pure set logic that provably preserves semantics.

The index file

One file per indexed root, in your cache directory (%LOCALAPPDATA%\grix or ~/.cache/grix) — repositories are never touched. Little-endian, mmap-friendly:

[magic][header][root path][paths blob][file table][trigram table][postings]
  • file table: fixed-width entries (path, size, mtime, flags) — the flags mark binary files (excluded) and oversized files (always scanned).
  • trigram table: sorted fixed-width entries; a posting list is found by binary search and decoded lazily.
  • postings: per-trigram sorted file ids, delta + LEB128 encoded. The linux kernel source (92,823 files, ~1.4 GB) indexes to 162 MiB with this scheme.

Every read is bounds-checked; a corrupted index produces an error (and a rebuild hint), never undefined behavior.

Incremental updates

grix index on an already-indexed tree:

  1. Walk the tree, collect (path, size, mtime), sort by path.
  2. Files whose (size, mtime) match the old index are reused: one linear pass over the old posting lists remaps their ids into the new file table — their bytes are never read again. The remap preserves sort order, so posting lists stay sorted by construction.
  3. Only new/changed files are read and extracted (in parallel).

In practice this makes a refresh ~20× faster than the initial build on a typical working tree.

The confirming scan

Candidates are scanned with regex's bytes API across a work-stealing thread pool. Match offsets are mapped to line numbers in a single forward pass (the newline counter doubles as the line-start anchor, so even pathological empty-match patterns stay linear). Files over 8 MiB are mmap'd instead of read.

Output mirrors ripgrep: headings on a tty, path:line:text when piped, --json for machines, exit codes 0/1/2 (match/no match/error).

Watch mode

By default a search refreshes the index first (a directory walk + stat; only changed files are re-read). On a large tree that walk is the dominant cost, so the --no-auto-index numbers above represent pure query speed but can be stale. grix watch removes that tension:

  1. It subscribes to filesystem events for the tree (notify: inotify / FSEvents / ReadDirectoryChangesW).
  2. Events are filtered (gitignore + .git) so build churn like target/ doesn't trigger work, then debounced — after ~400 ms of quiet it runs the same incremental build, re-reading only what changed.
  3. It writes a heartbeat to a sidecar file next to the index. A normal grix <pattern> checks that heartbeat: if a watcher is alive it skips its own refresh and trusts the live index — instant and fresh.

The heartbeat is a freshness timestamp, not a lock: if the watcher crashes the heartbeat goes stale within seconds and searches transparently resume refreshing themselves. Nothing in the repository is touched.

What grix does not do (yet)

  • Sub-file granularity: posting lists reference whole files; very large uniform corpora would benefit from chunk-level postings.
  • Incremental on-disk index: a watch reindex rewrites the whole index file. Cheap for typical repos; a true incremental format would help on giant trees.
  • Multiline patterns (-U) and replacements.