nish/regex

Regular expressions whose search time is linear in the input, whatever the pattern.

import {
  REGEX_MAX_CLASS_RANGES,
  REGEX_MAX_DEPTH,
  REGEX_MAX_GROUPS,
  REGEX_MAX_INSTRUCTIONS,
  REGEX_MAX_PROPERTY_RANGES,
  REGEX_MAX_REPEAT,
  Regex,
  RegexMatch,
  regexCompile,
  regexEscape,
} from "nish/regex";
import { Regex, RegexMatch, regexCompile } from "nish/regex";

const compiled = regexCompile("(?<year>\\d{4})-(?<month>\\d{2})", "")
if (compiled.isErr()) {
  // compiled.error is the reason, such as "regex: missing ) at byte 0"
} else {
  const re: Regex = compiled.value
  const m: RegexMatch = new RegexMatch()
  if (re.exec("due 2026-10", 0, m)) {
    // m.start() 4, m.end() 11, m.named("month") "10"
  }
  re.replaceAll("2026-10 and 2027-01", "$<month>/$<year>")  // "10/2026 and 01/2027"
}

The syntax is JavaScript's, with the u flag's strictness: literals, ., classes [a-z] and [^…], \d \w \s and their negations, \b \B ^ $, groups (…), (?:…) and (?<name>…), |, and the quantifiers * + ? {n} {n,} {n,m} with their lazy ? forms. Escapes are \n \r \t \f \v \0, \cX, \xHH, \uHHHH, \u{H…} and a backslash before any syntax character; a {, } or ] that does not belong to a quantifier or a class is an error rather than a literal, so write \{.

\p{…} and \P{…} are Unicode 16.0's properties as JavaScript names them: a General_Category value (L, Lu, Letter, gc=Nd), Script= or Script_Extensions= a script (sc=Grek, scx=Deva), or a binary property (Alphabetic, Emoji, ASCII, Any, Assigned). The flags are i, m (^ and $ at line terminators), s (. matches them too) and u, which changes nothing.

i folds A-Z to a-z, and above ASCII follows Unicode's simple case folding, so σ matches Σ and ς and [α-ω] the capitals; unlike JavaScript nothing folds across ASCII, so the Kelvin sign and ſ match no k or s, though under i both are word characters to \w, \W, \b and \B, as with JavaScript's iu. Backreferences and lookaround are refused at compile time: they are what makes a matcher backtrack, and this one never does.

A repeat count is at most 1,000, a pattern at most 100,000 instructions once its repeats are written out, 1,024 capturing groups and 10,000 ranges in one class, and its property escapes and case folding add at most 100,000 ranges to its classes.

Matching never backtracks

A search runs a lazy DFA first: it builds its states from the compiled program as the text needs them, so it reads a byte per step and the leftmost-first match's end comes from a table lookup. A reverse DFA, run back from that end, finds where the match starts, and a Pike VM, the construction RE2, Go's regexp and Rust's regex use, runs from that start only when a group's capture is wanted.

A pattern with a literal no match can avoid, such as \w+@example, is searched for by that literal and the match grown both ways from it. Every engine follows every alternative at once, so a match costs O(pattern × input) at worst and (a+)+$ against a thousand as and a b is as quick as a+$.

Finding every match (findAll, count, replaceAll, split) is one search per match, so it is quadratic when a preferred branch reads far ahead before a short one wins: <[^>]*>|< over a text of <s rereads the rest of the text for each, as it does in RE2 and Rust's regex. Which match is found is the one JavaScript finds — the leftmost, and of those the one the first alternative and the greediest quantifier prefer — and a group inside a quantifier keeps only its last iteration's capture, as in JavaScript.

An iteration past a quantifier's minimum that matches empty is rejected, as JavaScript rejects it. The VM keeps one thread per instruction, position and set of iterations begun, so (a*?)+?$ on "aa" captures "a", as JavaScript does; past three such quantifiers nested in one another the deeper ones share their threads, and a capture there can be a different iteration's than JavaScript's.

Strings are UTF-8 and offsets are bytes

Strings are UTF-8 and offsets are bytes, like s.length. The VM steps a code point at a time, so . and [^a] consume a whole character; a byte that is not part of valid UTF-8 is one character of its own, which no literal and no range matches. \w, \d and \b are ASCII, as they are in JavaScript; \s is JavaScript's whitespace, U+FEFF and U+3000 included. After an empty match findAll, replaceAll and split step one character.

What a call costs

The VM's two thread lists, its capture tables and its stack are allocated once by regexCompile. test tracks no captures, findAll and a replace whose template names no group track only the match's bounds, and only exec, find, split and a template with $1 or $<name> pay for every group.

A pattern that starts with a literal is searched for with s.indexOf; one whose first few bytes are each one of a set rare enough to be worth it, like [A-Z][a-z] or cat|dog, is searched for those bytes by a runtime kernel that tests sixteen or thirty-two starts at a time; any other whose first characters are known skips the bytes that cannot start a match with a 128-entry table; and a pattern that is nothing but a literal never starts an engine at all.

The DFA's states are built as searches need them and kept, so only a search that meets new states allocates, and only up to a bound: its table holds at most 2,048 states and 262,144 transitions (1 MiB), and a search that fills it clears it and goes on; one that keeps clearing it without reading at least 10 bytes per state hands the rest of the text to the VM, which is slower but never needs more memory. Because the scratch memory lives in the Regex, one Regex is used by one thread at a time.

Functions

regexCompile

Compile pattern with flags, a string of i, m, s and u in any order; u changes nothing, as patterns are always read by code point. The error names what is wrong and its byte in the pattern.

const regexCompile: (
  pattern: string,
  flags: string,
) => Result<Regex, string>
patternstringrequired

The pattern, in JavaScript's syntax without the slashes.

flagsstringrequired

Any of i (ignore case), m (^ and $ match at line ends), s (. matches a newline) and u, each at most once.

returnsResult<Regex, string>

The compiled pattern, or the reason it does not compile, such as "regex: missing ) at byte 0" or regex: invalid flags "x".

regexEscape

text with every syntax character escaped, so that it compiles to a pattern matching exactly text.

const regexEscape: (text: string) => string
textstringrequired

The literal text to match.

returnsstring

A pattern for regexCompile; text unchanged when it holds no syntax character.

Classes

Regex

A compiled pattern: its program, its classes, what the prefilters read and the VM's scratch memory. Made by regexCompile.

class Regex
Member
readonly flags: string The flags as written.
groups: i32 Capture groups, the whole match included.
readonly source: string The pattern as written.
count(text: string): i32 How many matches findAll would answer, without making their strings.
exec(text: string, from: i32, m: RegexMatch): boolean Search text from byte from and fill m with the first match and every group. Answers whether there was one; m is untouched when not. Reusing one RegexMatch makes a loop of searches allocate nothing.
find(text: string, from: i32): RegexMatch | null The first match at or after byte from.
findAll(text: string): string[] The text of every match, left to right, none overlapping. After an empty match the search resumes one character on.
groupCount(): i32 How many groups the pattern has.
groupIndex(name: string): i32 The number of a named group.
replace(text: string, replacement: string): string text with its first match replaced by replacement, which is String.prototype.replace's template: $$ is $, $& the match, $` and $' the text before and after it, $1 to $99 a group and $<name> a named one; a group that took no part is "".
replaceAll(text: string, replacement: string): string text with every match replaced by replacement, as replace reads it.
split(text: string): string[] text cut at every match, as String.prototype.split cuts it: each group's text follows the piece before its match ("" for one that took no part), an empty match where the last piece ended or at the end cuts nothing, and "" splits to nothing when the pattern matches it, else to [""].
test(text: string): boolean Whether the pattern matches anywhere in text.

RegexMatch

One match: the input it was found in and the byte offsets of every group.

class RegexMatch
Member
new RegexMatch() An empty match with no groups, for Regex.exec to fill in.
end(): i32 Where the match ends.
group(k: i32): string Group k's text.
groupCount(): i32 How many groups the pattern has.
groupEnd(k: i32): i32 Where group k ends.
groupStart(k: i32): i32 Where group k starts.
matched(k: i32): boolean Whether group k took part in the match.
named(name: string): string The text of a named group.
start(): i32 Where the match starts.
text(): string The matched text.

Limits

10,000

REGEX_MAX_CLASS_RANGES: i32

The most ranges one class may list; one more is a compile error.

250

REGEX_MAX_DEPTH: i32

How deeply groups may nest; a deeper pattern is a compile error.

1,024

REGEX_MAX_GROUPS: i32

The most capturing groups a pattern may have, past group 0; one more is a compile error. A name is checked against each.

100,000

REGEX_MAX_INSTRUCTIONS: i32

The most instructions a compiled pattern may have; regexCompile refuses a bigger program.

100,000

REGEX_MAX_PROPERTY_RANGES: i32

The most ranges the property escapes and case folding of one pattern may add to its classes; one more is a compile error.

1,000

REGEX_MAX_REPEAT: i32

The largest count {n}, {n,} or {n,m} may give; a larger one is a compile error.