embergrep

A grep-alike command-line tool whose regex engine is built entirely from scratch — no built-in RegExp, no re module, no library. It's a Thompson NFA: patterns compile to a small state machine and get matched by simulating every live path through it at once, character by character.

Why it's interesting

Regex engines that backtrack (PCRE, Python's re, JavaScript's RegExp) can go exponential on patterns like (a+)+b run against a string with no trailing b — the engine tries every way the inner a+ could have split up the input before giving up. This one can't: because it tracks the whole set of possible NFA states simultaneously instead of trying alternatives one at a time and back­tracking on failure, matching a pattern of size m against text of length n is always O(m·n), never exponential. test/matcher.test.ts proves it — 5,000 as against (a+)+b resolves in single-digit milliseconds instead of never finishing.

The unanchored search that grep needs (find a match anywhere on the line) is folded into the same single pass using thread priority: a fresh candidate start position is injected at the lowest priority on every step, so earlier-starting threads always win, giving correct leftmost matching without rescanning from every position.

Install / run

Requires Node.js 18+.

npm install
npm run build
node dist/src/cli.js --help

Or install it as a local command:

npm install -g .
embergrep --help

Usage example

$ cat examples/sample.txt
The quick brown fox jumps over the lazy dog.
Order #4471 shipped to 221B Baker Street on 2024-03-15.
contact: alice@example.com, bob@example.org
error: connection refused (errno 111)
warning: disk usage at 87%
CamelCaseIdentifier_42 and snake_case_identifier
2024-03-15T10:22:00Z INFO service started
2024-99-99T00:00:00Z INFO not a real date

$ embergrep -n "error|warning" examples/sample.txt
4:error: connection refused (errno 111)
5:warning: disk usage at 87%

$ embergrep "\w+@\w+\.\w+" examples/sample.txt
contact: alice@example.com, bob@example.org

$ embergrep -c "\d+" examples/sample.txt
6

Matches are highlighted in the matched span when stdout is a TTY (force with --color, disable with --no-color). It also reads from stdin when no files are given, just like real grep.

Supported pattern syntax

Syntax	Meaning
abc	literal characters
.	any character except newline
a|b	alternation
a* a+ a?	zero-or-more, one-or-more, optional
a{2,4} a{2,} a{3}	bounded / unbounded repeat
[abc] [a-z] [^a-z]	character class, range, negated class
\d \w \s (and \D \W \S)	digit / word / whitespace shorthand
^ $	start / end of line
(...)	grouping
\. \* \( ...	escape a metacharacter to match it literally

CLI flags

-n, --line-number   prefix matches with their 1-based line number
-c, --count         print only a count of matching lines per file
-v, --invert-match  print lines that do NOT match
    --color         force ANSI highlighting of the matched span
    --no-color      disable ANSI highlighting
-h, --help          show help

How it works

1. Parse (src/parser.ts) — a recursive-descent parser turns the pattern string into an AST (src/ast.ts): concatenation, alternation, repetition, character classes, anchors, groups.
2. Compile (src/nfa.ts) — the AST is compiled to an NFA using Thompson's construction: each AST node becomes a small fragment of states wired together with epsilon (no-input) transitions, built up recursively into the full machine. Character classes compile to one state holding a predicate function rather than an alternation of single characters, so \w doesn't blow up into dozens of states.
3. Match (src/matcher.ts) — the NFA is simulated à la Pike's VM / RE2: instead of choosing one path and backtracking on failure, the matcher advances a priority-ordered set of live threads one input character at a time. Epsilon-closures resolve splits and check ^/$ assertions against the current position. The first thread (in priority order) to reach the accepting state wins, which naturally yields leftmost, greedy matching in a single linear pass.
4. CLI (src/cli.ts) — a thin grep-shaped wrapper over the library (src/index.ts): reads files or stdin, applies the compiled pattern per line, and formats output.

Tests

npm test

24 unit tests cover parsing edge cases (unbalanced groups/classes, invalid repeat bounds), matching semantics (alternation, quantifiers, classes, shorthand classes, anchors, grouping, leftmost-longest search), and the catastrophic-backtracking safety property described above.