GitHub - dawsonhuang0/posix-regex: POSIX standard RegExp, faster than glibc.

POSIX basic and extended regular expressions for JavaScript, with the leftmost-longest matching the standard asks for and JavaScript's own RegExp cannot give you.

An independent implementation, written from the POSIX specification. MIT licensed.

import { PsxRegExp, match } from 'posix-regex';

// POSIX takes the longest match, not the first alternative that fits.
match('a|ab', 'abc', 'e')?.value; // 'ab'
/a|ab/.exec('abc')?.[0];          // 'a'

// A PsxRegExp goes wherever a RegExp goes.
const dates = new PsxRegExp('([0-9]{4})-([0-9]{2})-([0-9]{2})', 'ge');
'due 2026-08-04'.replace(dates, '$3/$2/$1'); // 'due 04/08/2026'
[...dates.exec('due 2026-08-04')];           // ['2026-08-04', '2026', '08', '04']

Why not RegExp?

RegExp is a Perl-style backtracking engine. POSIX regular expressions are a different language with different answers.

Usage

import { PsxRegExp } from 'posix-regex';

const comment = new PsxRegExp('^[[:space:]]*#', 'gme');

It is a RegExp in shape: same flags, same lastIndex, same exec result, and the same well-known symbols. So exec, test, source, flags, and input.match, input.matchAll, input.search, input.replace, input.replaceAll and input.split all do what you already expect, down to where lastIndex lands and how split splices in groups.

The rest of this section is only what is not the same.

Three flags

d, g, i, m and y are the host's exactly. The others:

• e is ours — extended syntax (ERE). The host has one syntax and needs no such flag; POSIX has two and defaults to basic, where a|b is three literal characters. You will want this flag.
• s is already on. POSIX . covers a newline, so only m takes it away and s is how you put it back. ms then behaves as the host's ms does.
• u is always in force and accepted for portability: the subject is read by code point whatever you ask. v is rejected — POSIX bracket expressions have no set notation.

Options the host has no room for

Every flag has a named form (ignoreCase, global, dotAll, …), and passing an object instead of a string is the only way to reach these three:

Every method also has a pattern-side spelling — regex.matchAll(input), regex.split(input, limit?), regex.replace(input, …) — taking a trailing options object with from, notAtLineStart and notAtLineEnd. The last two matter when searching a buffer piece by piece and ^ or $ should not fire at the seam; from overrides lastIndex for that one call.

Three extra fields on a result

A result is the array of matched strings, exactly as the host's is — found[0], .index, .input, .groups, and .indices under d. Alongside them:

const found = new PsxRegExp('([[:alpha:]]+) ([[:alpha:]]+)', 'e')
  .exec('say hello now')!;

found.value;       // 'say hello'  — the whole match, named
found.end;         // 9            — one past the end
found.captures[2]; // { start: 4, end: 9, value: 'hello' }

Dialects

Dialects are modelled as spellings: what is ( in one is \( in another.

compile('a+',   { flavor: 'basic' }).test('aaa');    // false — '+' is the sign
compile('a\\+', { flavor: 'basic' }).test('aaa');    // true
compile('a+',   { flavor: 'extended' }).test('aaa'); // true

// Or say how the operators are written yourself.
compile('a+b', { flavor: { plus: 'bare', group: 'bare' } });

Collation

POSIX defines [a-z] by the collation order of the locale, which agrees with character codes only in the C locale — the default here.

compile('[a-Z]+', { flavor: 'extended' });
// PatternError: invalid-range — 'a' is after 'Z' by character code

compile('[a-Z]+', { flavor: 'extended', collation: 'en' }).exec('abzABZ')?.value;
// 'abzABZ' — a dictionary puts 'a' before 'Z'

compile('[[=a=]]+', { flavor: 'extended', collation: 'en' }).exec('aáAà')?.value;
// 'aáAà' — an equivalence class covers accented and cased forms

Errors

try {
  compile('a[b', { flavor: 'extended' });
} catch (error) {
  error.code;      // 'unbalanced-bracket'
  error.posixName; // 'REG_EBRACK'
  error.at;        // where the reader gave up
}

quote(text) escapes text so it matches itself in either dialect — which is why it produces [(] rather than \(, since in basic syntax \( is the group operator.

How it works

A pattern is read by the POSIX grammar into an expression tree, then turned into a graph of single steps: reading a character, opening a group, closing one, testing an anchor. Counted repetitions are written out as copies, so a{200} really is two hundred steps.

Matching runs forward from the start position, carrying the whole set of steps the pattern could be at. Where two readings arrive at the same step, the one the standard prefers goes on alone, so nothing is ever written down twice and nothing is backtracked.

Following the GNU C Library instead takes a different route over the same graph — forward, then backward from the end dropping every step that cannot reach it, then one committed walk that reads off the groups — because that is what the library does, and reproducing its answers means reproducing its method.

How far the match reaches is worked out a table lookup at a time: which steps are reachable after reading a character depends on nothing but which were reachable before it, that character, and what stood behind, so the answer is worked out once and remembered. After the first few characters of a subject almost every lookup is a hit, and a character costs one.

Where the groups fall is worked out the same way. The path each reading takes between two characters is fixed by that same pair, so it too is settled once, as a list of registers to write — and a character costs a copy of them and a handful of writes rather than a walk over the pattern. The exception is a character where two readings run together at one step: those have to be weighed against each other, which no plan can do in advance, and the walk settles them.

compile('(a*)*b', { flavor: 'extended' }).test('a'.repeat(8000)); // ~1ms, false
/(a*)*b/.test('a'.repeat(8000));                                  // hangs

Against the C library, on the same patterns and subjects:

The last of those never follows a step at all: a pattern that cannot begin with a character above ASCII is looked for as a handful of characters, which the host searches for an order of magnitude faster than for a handful plus a range — so ruling a subject out costs one pass and nothing else.

Back-references are the exception: what such a pattern accepts depends on text it captured earlier, so it cannot be run over the input alone. Those are matched by walking the expression directly, bounded by stepLimit, which throws MatchLimitError rather than running forever.

A pattern whose graph grows past 40,000 steps is refused with pattern-too-large. Following the C library asks more of the graph — it has to carry every condition onto copies of what follows — so a few shapes are refused in that mode alone: a repetition nested inside a repetition inside another, which the C original itself takes seconds over. The default answers those.

Which answer you get

POSIX fixes which extent a match has — leftmost, then longest — and applies the same rule to each group in turn. Implementations differ on the second half, and the GNU C Library's answer is often not the one the standard asks for. This package follows the standard, so where the two part company it is the library that is out, not this:

// The first group takes "ab", the longest it can, even though the alternation
// is written the other way round. GNU grep answers ['abcd', 'a', 'bcd', ''].
match('(a|ab)(c|bcd)(d*)', 'abcd', { flavor: 'extended' })?.groups;
// ['abcd', 'ab', 'c', 'd']

Conformance

Checked against the five corpora the GNU C Library uses on its own regex engine — 2,129 cases, run by npm run conformance against a glibc source tree:

BOOST.tests runs with collation: 'en', matching the locale its expectations were recorded in. 27 cases are skipped: they exercise REG_NOSPEC, REG_STARTEND and REG_PEND, which are C-buffer interfaces with no meaning here.

Two things the standard leaves to be read out of its rule, which those suites pin down and this package follows:

• A repetition spends a round on nothing only where it spends no other round. (a*)* against "bc" is allowed the one empty round that lets its group take part; the repetition in a(b+|((c)*))+d against "abd" has a round that reads, so it gets no empty one and ((c)*) stands aside.
• Where the rounds could be divided up differently, the earlier ones are as long as they go, which leaves the last — the one reported — the shortest it can be.

Beyond the suites, npm run oracle checks matching against an exhaustive reading of the pattern: every way it can match, ranked by the rule. The two share only the ranking — finding the best reading under it, which is the part with the interesting bugs, they do quite differently. Over 22,692 generated cases they agree on all 22,692 extents and on the groups in 99.76% of them.

The 55 that differ are all one thing, and worth knowing about. Two readings are weighed at each step, and where they are level on everything settled so far they may still differ in a group that a later round will overwrite — and the rule weighs that group by what it finally holds, which is not yet known. So a reading is occasionally dropped that would have won at the end, and a group inside a repetition is left unset, or set to a shorter span, than the standard asks. The extent of the match is never affected. Answering these exactly means carrying the history of every group rather than its current value; carrying several readings per step instead was tried, and made matters slightly worse.

Not implemented

• Multi-character collating elements. [[.ae.]] is rejected as invalid-collating-element; single-character ones work, and ordering follows the collation option. No locale API exposes a table of a locale's named collating symbols.
• The C buffer interfaces. REG_STARTEND and REG_PEND have no JavaScript equivalent; from, notAtLineStart and notAtLineEnd cover what they were for.
• The host's syntax extensions. Lookaround, named groups, non-capturing (?:), lazy quantifiers and \d-style shorthands are Perl, not POSIX, and none of them are here. The interface is the host's; the language is not.

Two smaller differences from the host, both deliberate: matchAll does not insist on the g flag, since it walks the subject itself and has no lastIndex to run away with; and the source of an empty pattern is '' rather than (?:), which POSIX has no way to spell.

One TypeScript wrinkle: String.prototype.matchAll is typed to RegExp itself rather than to [Symbol.matchAll], so input.matchAll(regex) needs a cast even though it runs. The other five String methods are typed to their symbols and need none — and regex.matchAll(input) is the better spelling anyway.

Character classes are Unicode-aware above ASCII, matching a C library in a UTF-8 locale, and matching works on characters, so an astral character counts as one.

Licence and provenance

See LICENSE.