miniregex-rs

Mirrors: Codeberg | git.lesleylai.info

A simple non-backtracking NFA-based implementation of regular expressions.

It also contains a web app for visualizing the algorithm. See it alive at miniregex.lesleylai.info.

Features

• Guarantees O(n * m) time complexity for matching (where n is the length of the input string and m is the length of the regex)
  • This prevents ReDoS vulnerabilities
• A web-based visualizer for regex matching algorithm (thanks to WebAssembly)
• UTF-8 characters support (thanks Rust)

Supported Syntax

Miniregex currently only supports a small subset of the syntax of regular expressions from you may see in other engines:

• Repetitions: *, +, ?
• Union: |
• Grouping: (...)
• Any Character: .
• Escaped literal characters: e.g. \., \*, and \(
• Bracketed Character Classes
  • ranges: e.g. [a-z]
  • union of multiple character classes: e.g. [a-zA-Z_]
  • Negated character classes: e.g. [^a-zA-Z]

All other characters are treated as literal characters.

Packages

• crates/miniregex-core: Core parsing, NFA construction, and execution logic for miniregex.
• crates/miniregex-web: The web app visualizes regex matching algorithm