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"
}
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.
regexEscape
text with every syntax character escaped, so that it compiles to a pattern matching exactly text.
Regex
A compiled pattern: its program, its classes, what the prefilters read and the VM's scratch memory.
RegexMatch
One match: the input it was found in and the byte offsets of every group.
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>
patternstringrequiredThe pattern, in JavaScript's syntax without the slashes.
flagsstringrequiredAny 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
textstringrequiredThe literal text to match.
returnsstringA 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.

