Regex Utils

Zero-dependency TypeScript library for regex utilities that go beyond string matching. These are surprisingly hard to come by for any programming language. ✨

• Documentation
• Online demos:
  • RegExp Equivalence Checker
  • Random Password Generator

API Overview 🚀

• 🔗 Set-style operations:
  • .and(...) - Compute intersection of two regex.
  • .not() - Compute the complement of a regex.
  • .without(...) - Compute the difference of two regex.
• ✅ Set-style predicates:
  • .isEquivalent(...) - Check whether two regex match the same strings.
  • .isSubsetOf(...)
  • .isSupersetOf(...)
  • .isDisjointFrom(...)
  • .isEmpty() - Check whether a regex matches no strings.
• 📜 Generate strings:
  • .sample(...) - Generate random strings matching a regex.
  • .enumerate() - Exhaustively enumerate strings matching a regex.
• 🔧 Miscellaneous:
  • .size() - Count the number of strings that a regex matches.
  • .derivative(...) - Compute a Brzozowski derivative of a regex.
• and others...

Installation 📦

npm install @gruhn/regex-utils
Copy

import { RB } from '@gruhn/regex-utils'
Copy

Syntax Support

Feature	Support	Examples
Quantifiers	✅	a*, a+, a{3,10}, a?
Lazy Quantifiers	✅	a*?, a+?, a{3,10}?, a??
Alternation	✅	a|b
Character classes	✅	., \w, [a-zA-Z], ...
Escaping	✅	\$, \., ...
(Non-)capturing groups	✅	(?:...), (...)
Start/end anchors	⚠️1	^, $
Lookahead	⚠️2	(?=...), (?!...)
Lookbehind	⚠️2	(?<=...), (?<!...)
Word boundary	❌	\b, \B
Unicode property escapes	❌	\p{...}, \P{...}
Backreferences	❌	\1 \2 ...
dotAll flag	✅	/.../s, (?s:...)
global flag	✅	/.../g
hasIndices flag	✅	/.../d
ignoreCase flag	❌	/.../i (?i:...)
multiline flag	❌	/.../m (?m:...)
unicode flag	❌	/.../u
unicodeSets flag	❌	/.../v
sticky flag	❌	/.../y

1. Some complex patterns are not supported like anchors inside quantifiers (^a)+ or anchors inside lookaheads (?=^a).
2. Not supported are nested lookaheads/lookbehinds like (?=a(?=b)) and lookaheads/lookbehinds combinations like (?=a)b(?<=c).

An UnsupportedSyntaxError is thrown when unsupported patterns are detected. The library SHOULD ALWAYS either throw an error or respect the regex specification exactly. Please report a bug if the library silently uses a faulty interpretation.

Handling syntax-related errors:

import { RB, ParseError, UnsupportedSyntaxError } from '@gruhn/regex-utils'

try {
  RB(/^[a-z]*$/)
} catch (error) {
  if (error instanceof SyntaxError) {
    // Invalid regex syntax! Native error, not emitted by this library.
    // E.g. this will also throw a `SyntaxError`: new RegExp(')')
  } else if (error instanceof ParseError) {
    // The regex syntax is valid but the internal parser could not handle it.
    // If this happens it's a bug in this library.
  } else if (error instanceof UnsupportedSyntaxError) {
    // Regex syntax is valid but not supported by this library.
  }
}
Copy

Example use cases 💡

Generate test data from regex 📜

Generate 5 random email addresses:

const email = RB(/^[a-z]+@[a-z]+\.[a-z]{2,3}$/)
for (const str of email.sample().take(5)) {
  console.log(str)
}
Copy

ky@e.no
cc@gg.gaj
z@if.ojk
vr@y.ehl
e@zx.hzq
Copy

Generate 5 random email addresses, which have exactly 20 characters:

const emailLength20 = email.and(/^.{20}$/)
for (const str of emailLength20.sample().take(5)) {
  console.log(str)
}
Copy

kahragjijttzyze@i.mv
gnpbjzll@cwoktvw.hhd
knqmyotxxblh@yip.ccc
kopfpstjlnbq@lal.nmi
vrskllsvblqb@gemi.wc
Copy

Refactor regex then check equivalence 🔄

ONLINE DEMO

Say we found this incredibly complicated regex somewhere in the codebase:

const oldRegex = /^a|b$/
Copy

This can be simplified, right?

const newRegex = /^[ab]$/
Copy

But to double-check we can use .isEquivalent to verify that the new version matches exactly the same strings as the old version. That is, whether oldRegex.test(str) === newRegex.test(str) for every possible input string:

RB(oldRegex).isEquivalent(newRegex) // false
Copy

Looks like we made some mistake. We can generate counterexamples using .without(...) and .sample(...). First, we derive new regex that match exactly what newRegex matches but not oldRegex and vice versa:

const onlyNew = RB(newRegex).without(oldRegex)
const onlyOld = RB(oldRegex).without(newRegex)
Copy

onlyNew turns out to be empty (onlyNew.isEmpty() === true) but onlyOld has some matches:

for (const str of onlyOld.sample().take(5)) {
  console.log(str)
}
Copy

aaba
aa
aba
bab
aababa
Copy

Why does oldRegex match all these strings with multiple characters? Shouldn't it only match "a" or "b" like newRegex? Turns out we thought that oldRegex is the same as ^(a|b)$ but in reality it's the same as (^a)|(b$).

Comment regex using complement 💬

How do you write a regex that matches HTML comments like:

<!-- This is a comment -->
Copy

A straightforward attempt would be:

<!--.*-->
Copy

The problem is that .* also matches the end marker -->, so this is also a match:

<!-- This is a comment --> and this shouldn't be part of it -->
Copy

We need to specify that the inner part can be any string that does not contain -->. With .not() (aka. regex complement) this is easy:

import { RB } from '@gruhn/regex-utils'

const commentStart = RB('<!--')
const commentInner = RB(/^.*-->.*$/).not()
const commentEnd = RB('-->')

const comment = commentStart.concat(commentInner).concat(commentEnd)
Copy

With .toRegExp() we can convert back to a native JavaScript regex:

comment.toRegExp()
Copy

/^<!--(---*[^->]|-?[^-])*---*>$/
Copy

Password regex using intersections 🔐

ONLINE DEMO

It's difficult to write a single regex for multiple independent constraints. For example, to specify a valid password. But with regex intersections it's very natural:

import { RB } from '@gruhn/regex-utils'

const passwordRegex = RB(/^[a-zA-Z0-9]{12,32}$/) // 12-32 alphanumeric characters
  .and(/[0-9]/) // contains a number
  .and(/[A-Z]/) // contains an upper case letter
  .and(/[a-z]/) // contains a lower case letter
Copy

We can convert this back to a native JavaScript RegExp with:

passwordRegex.toRegExp()
Copy

We can also use other utilities like .size() to determine how many potential passwords match this regex:

console.log(passwordRegex.size())
Copy

2301586451429392354821768871006991487961066695735482449920n
Copy

With .sample() we can generate some of these matches:

for (const str of passwordRegex.sample().take(10)) {
  console.log(str)
}
Copy

NEWJIAXQISWT0Wwm
lxoegadrzeynezkmtfcIBzzQ9e
ypzvhvtwpWk4u6
MSZXXKIKEKWKXLQ8HQ7Ds
BCBSFBSMNOLKlgQN5L
8950244600709IW1pg
UOTQBLVOTZQWFSAJYBXZNQBEeom0l
520302447164378435bv4dp4ysC
71073970686490eY2Jt4
afgpnxqwUK5B
Copy

Solve Advent Of Code 2023 - Day 12 🎄

In the coding puzzle Advent Of Code 2023 - Day 12 you are given pairs of string patterns. An example pair is .??..??...?##. and 1,1,3. Both patterns describe a class of strings and the task is to count the number of strings that match both patterns.

In the first pattern, . and # stand for the literal characters "dot" and "hash". The ? stands for either . or #. This can be written as a regular expression:

• for # we simply write #
• for . we write o (since . is a reserved symbol in regular expressions)
• for ? we write (o|#)

So the pattern .??..??...?##. would be written as:

const firstRegex = /^o(o|#)(o|#)oo(o|#)(o|#)ooo(o|#)##o$/
Copy

In the second pattern, each digit stands for a sequence of # separated by at least one o. This can also be written as a regular expression:

• For a digit like 3 we write #{3}.
• Between digits we write o+.
• Additionally, arbitrary many o are allowed at the start and end, so we add o* at the start and end.

Thus, 1,1,3 would be written as:

const secondRegex = /^o*#{1}o+#{1}o+#{3}o*$/
Copy

To solve the task and find the number of strings that match both regex, we can use .and(...) and .size() from regex-utils. .and(...) computes the intersection of two regular expressions. That is, it creates a new regex which exactly matches the strings matched by both input regex.

const intersection = RB(firstRegex).and(secondRegex)
Copy

With .size() we can then determine the number of matched strings:

console.log(intersection.size())
Copy

4n
Copy

While at it, we can also try .enumerate() to list all these matches:

for (const str of intersection.enumerate()) {
  console.log(str)
}
Copy

oo#ooo#ooo###o
o#oooo#ooo###o
oo#oo#oooo###o
o#ooo#oooo###o
Copy

For a full solution checkout: ./benchmark/aoc2023-day12.ts.

References 📖

Heavily informed by these papers:

• https://www.khoury.northeastern.edu/home/turon/re-deriv.pdf
• https://courses.grainger.illinois.edu/cs374/fa2017/extra_notes/01_nfa_to_reg.pdf