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
• 🔍 RegExp Equivalence Checker

API Overview 🚀

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

Installation 📦

npm install @gruhn/regex-utils
Copy

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

Example Use Cases 💡

Refactor Regex and Check Equivalence 🔄

Say we identified a regex in the code base that is prone to catastrophic backtracking and came up with a new version:

const oldRegex = /^(?:[a-zA-Z]\:\\|\\\\)([^\\\/\:\*\?\<\>\"\|]+(\\){0,1})+$/
const newRegex = /^(?:[a-zA-Z]:\\|\\\\)([^\\\/\:*?<>"|]+\\?)+$/
Copy

Using .isEquivalent we can verify that the refactored 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) // true
Copy

There is also a web interface for checking regex equivalence which also shows counterexample strings if the two regular expressions are not equivalent. The source code is a single HTML file: ./equiv-checker.html.

Comment Regex using Complement 💬

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

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

A straight forward 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 strContainingCommentEnd = RB(/.*-->.*/)

const commentRegex = RB('<!--')
  .concat(strContainingEndMarker.not())
  .concat('-->')
Copy

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

commentRegex.toRegExp()
Copy

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

Password Regex using Intersections 🔐

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]/) // at least one number
  .and(/[A-Z]/) // at least one upper case letter   
  .and(/[a-z]/) // at least one 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 .enumerate() we can list some of these matches:

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

aaaaaaaaaaA0
aaaaaaaaaa0A
aaaaaaaaaAA0
aaaaaaaaaA00
aaaaaaaaaaA1
aaaaaaaaa00A
baaaaaaaaaA0
AAAAAAAAAA0a
aaaaaaaaaAA1
aaaaaaaaaa0B
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 . has a special meaning 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