Reggie - Hybrid Compile-Time and Runtime Optimized Regex for Java

Reggie is a high-performance Java regex library that provides two complementary approaches to pattern matching:

Compile-Time Generation - Zero runtime overhead via annotation processing
Runtime Compilation - Lazy bytecode generation with automatic caching

Both approaches analyze each pattern and route it to one of three strategy families — DFA-backed (deterministic, longest-match), NFA/PikeVM-backed (Thompson construction, leftmost-first), or bounded-backtracking bytecode (shape-restricted, still O(n)) — then generate specialized bytecode. For patterns without backreferences, lookaround, atomic groups, possessive quantifiers, conditionals or recursion, one match or find call takes linear time in the input length. Patterns with those features have no linear-time guarantee. The ones that no specialized strategy can run go to a memoized backtracker whose work is polynomial, with step budgets that throw MatchBudgetExceededException instead of hanging. See Known Limitations.

Why Reggie?

Traditional Java regex engines (like java.util.regex.Pattern) have several drawbacks:

Runtime compilation overhead: Patterns must be compiled every time your application starts
Backtracking complexity: Worst-case exponential time complexity (ReDoS vulnerabilities)
No compile-time validation: Pattern errors only discovered at runtime
Interpreter overhead: Pattern execution through a generic interpreter

Reggie solves these problems:

Feature	JDK Pattern	Reggie (Compile-Time)	Reggie (Runtime)
Compilation overhead	Every startup	Zero (at build time)	First use only (~5-10ms)
ReDoS protection	❌ No	✅ Yes (linear or step-bounded²)	✅ Yes (linear or step-bounded²)
Error detection	Runtime	Compile time	Runtime
Performance	Good	Excellent (10-20x)	Excellent (10-20x)
JIT optimization	Limited	Maximum	Maximum
Dynamic patterns	✅ Yes	❌ No	✅ Yes

Quick Start

Runtime API (Simplest)

No build configuration needed - just use it:

import com.datadoghq.reggie.Reggie;
import com.datadoghq.reggie.runtime.ReggieMatcher;

public class Example {
    public static void main(String[] args) {
        // Compile pattern once (cached automatically)
        ReggieMatcher phone = Reggie.compile("\\d{3}-\\d{3}-\\d{4}");

        // Use it multiple times - fast!
        System.out.println(phone.matches("123-456-7890")); // true
        System.out.println(phone.matches("invalid"));       // false

        // Find in text
        System.out.println(phone.find("Call 123-456-7890"));  // true
        System.out.println(phone.findFrom("Call 123-456-7890", 0)); // 5
    }
}

First-use latency: ~5-10ms for pattern compilation, then <1µs cache lookup.

Compile-Time API (Zero Overhead)

Define patterns at compile time for maximum performance:

Step 1: Create a pattern provider class:

// MyPatterns.java
import com.datadoghq.reggie.ReggiePatterns;
import com.datadoghq.reggie.annotations.RegexPattern;
import com.datadoghq.reggie.runtime.ReggieMatcher;

public abstract class MyPatterns implements ReggiePatterns {

    @RegexPattern("\\d{3}-\\d{3}-\\d{4}")
    public abstract ReggieMatcher phone();

    @RegexPattern("[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}")
    public abstract ReggieMatcher email();

    @RegexPattern("\\b(?:[0-9]{1,3}\\.){3}[0-9]{1,3}\\b")
    public abstract ReggieMatcher ipv4();
}

Step 2: Use the patterns (implementation generated at compile time):

import com.datadoghq.reggie.Reggie;

public class Example {
    public static void main(String[] args) {
        // Get pattern provider instance (generated implementation)
        MyPatterns patterns = Reggie.patterns(MyPatterns.class);

        // Use the matchers - zero overhead!
        System.out.println(patterns.phone().matches("123-456-7890"));  // true
        System.out.println(patterns.email().matches("user@example.com")); // true
        System.out.println(patterns.ipv4().matches("192.168.1.1"));      // true
    }
}

First-use latency: 0ms (compiled at build time).

Performance

Reggie is faster than JDK's Pattern and RE2J on typical patterns because it compiles each pattern to specialized bytecode instead of interpreting a generic instruction stream. We don't publish specific speedup multipliers here: the only benchmark run on file predates the most recent performance work (6841723, 5db1866) and is not committed to this repo, so it cannot be trusted as a current number. Run the command below to generate a report for your own JVM/hardware/patterns.

Full Report

Run ./gradlew :reggie-benchmark:benchmarkAndReport to generate a detailed HTML report comparing Reggie, JDK Pattern, and RE2J across match/find/group-extraction/backreference/assertion/split categories.

Why So Fast?

Zero initialization: No Pattern.compile() overhead
Specialized bytecode: Each pattern gets custom-generated code, not a generic interpreter loop
Maximum JIT optimization: HotSpot can fully inline specialized matchers
No interpreter: Direct execution, no generic pattern interpreter
Bounded matching cost: for patterns without backreferences, lookaround, atomic groups, possessive quantifiers, conditionals or recursion, strategy selection picks a DFA, NFA/PikeVM, or bounded-backtracking bytecode strategy whose match or find call is O(n). Patterns with those features that no specialized strategy can run go to a memoized backtracker whose work is polynomial and capped by step budgets²

Engine Comparison

Feature	Reggie	JDK Pattern	RE2J
Time Complexity	O(n) per call for regular patterns³; not guaranteed otherwise²¹	O(2^n) worst case	O(n) guaranteed
Implementation	JIT-compiled bytecode	Interpreted backtracking	NFA simulation
ReDoS Safe	✅ Yes¹ ² ³	❌ No	✅ Yes
Backreferences	✅ Yes	✅ Yes	❌ No
Lookahead/Lookbehind	✅ Yes	✅ Yes	❌ No

¹ Applies to Reggie.compile() (default, native engine only — throws UnsupportedPatternException rather than silently degrading). Opting into compileAllowingFallback() / ReggieOption.ALLOW_JDK_FALLBACK delegates unsupported patterns to java.util.regex, which inherits JDK's backtracking worst case and is not ReDoS-safe. See doc/agents-fallback-and-limitations.md.

² Patterns with backreferences, lookaround, atomic groups, possessive quantifiers, conditionals or recursion that no linear strategy can run go to BackrefBacktrackMatcher, a backtracker memoized on (state, position, referenced group spans, loop counters). Its work is polynomial in the input length, not linear. Each match attempt stops after 2,000,000 steps (-Dreggie.countedloop.maxSteps). The attempts of one find call share a second budget of 2,000,000 plus 16,384 per searched character (-Dreggie.countedloop.stepsPerChar), which counts both steps and backreference characters compared. Both throw MatchBudgetExceededException, so an adversarial input ends in bounded time with an exception instead of a match result. RE2J accepts none of these features. ReDoSLinearityBenchmark measures how find() time grows with input length for Reggie, RE2J and java.util.regex.

³ The bound holds for one call. Iterating m matches over one input (findAll, repeated findFrom) can cost O(n · m) on the DFA strategies; see doc/agents-fallback-and-limitations.md.

Performance Tuning

Optional: Enable Zero-Copy String Access

TL;DR: Add this JVM argument for a modest additional performance boost (exact magnitude depends on your JVM/patterns — not independently benchmarked at current HEAD):

--add-opens java.base/java.lang=ALL-UNNAMED

How It Works

Reggie uses a smart multi-tier strategy for accessing string content during pattern matching:

Zero-Copy Mode (requires --add-opens): Direct access to String's internal byte array via MethodHandles - fastest
Copy-Based Mode (automatic fallback): Copies string bytes once, enables SIMD optimizations - very fast
charAt Mode (for specific patterns): Delegates to String.charAt() - still fast

The library works perfectly without any JVM arguments - it automatically falls back to copy-based or charAt mode. However, adding --add-opens eliminates the O(n) copy overhead for an extra performance edge.

When Zero-Copy Matters Most

The performance gain from --add-opens depends on your patterns:

Pattern Type	Impact	Example
Short strings (<100 chars)	Minimal (~1-2%)	Short validation patterns
Long strings + SIMD patterns	Moderate (~5%)	`[0-9a-fA-F]+` on large text
Tight loops, hot paths	Noticeable (~10%)	Millions of matches/sec
Anchored patterns	None	`^abc` (early bailout)

Adding the JVM Argument

Gradle:

tasks.withType(JavaExec) {
    jvmArgs '--add-opens', 'java.base/java.lang=ALL-UNNAMED'
}

test {
    jvmArgs '--add-opens', 'java.base/java.lang=ALL-UNNAMED'
}

Maven:

<build>
    <plugins>
        <plugin>
            <groupId>org.apache.maven.plugins</groupId>
            <artifactId>maven-surefire-plugin</artifactId>
            <configuration>
                <argLine>--add-opens java.base/java.lang=ALL-UNNAMED</argLine>
            </configuration>
        </plugin>
    </plugins>
</build>

Command Line:

java --add-opens java.base/java.lang=ALL-UNNAMED -jar your-app.jar

IDE (IntelliJ IDEA):

Run → Edit Configurations
Add to "VM options": --add-opens java.base/java.lang=ALL-UNNAMED

Verification

Check if zero-copy is active:

import com.datadoghq.reggie.runtime.StringView;

if (StringView.isZeroCopyAvailable()) {
    System.out.println("Zero-copy optimization enabled!");
} else {
    System.out.println("Using copy-based fallback (still fast!)");
}

Bottom line: The library works great out-of-box. Add --add-opens if you want to squeeze out every last microsecond in high-throughput scenarios.

Installation

Gradle

Add to your build.gradle:

repositories {
    mavenCentral() // or your repository
}

dependencies {
    // Reggie (runtime API + bundled annotation processor)
    implementation 'com.datadoghq:reggie:<version>'

    // Add for compile-time API (annotation processing)
    annotationProcessor 'com.datadoghq:reggie:<version>'
}

Maven

Add to your pom.xml:

<dependencies>
    <!-- Reggie (runtime API + bundled annotation processor) -->
    <dependency>
        <groupId>com.datadoghq</groupId>
        <artifactId>reggie</artifactId>
        <version><!-- version --></version>
    </dependency>
</dependencies>

Complete Usage Guide

Runtime Patterns

The runtime API compiles patterns on-demand with automatic caching.

Basic Usage

import com.datadoghq.reggie.Reggie;
import com.datadoghq.reggie.runtime.ReggieMatcher;

// Compile pattern (automatically cached)
ReggieMatcher matcher = Reggie.compile("\\d{3}-\\d{3}-\\d{4}");

// Test if entire string matches
boolean matches = matcher.matches("123-456-7890");  // true

// Find pattern anywhere in string
boolean found = matcher.find("Call 123-456-7890 now");  // true

// Find pattern starting at position
int position = matcher.findFrom("Multiple: 123-456-7890 and 999-888-7777", 0);
// Returns 10 (start of first match)

Cache Management

// Automatic caching (pattern string is the key)
ReggieMatcher m1 = Reggie.compile("\\d+");
ReggieMatcher m2 = Reggie.compile("\\d+");
assert m1 == m2;  // Same instance returned

// Explicit cache key for user input
String userPattern = getUserInput();
ReggieMatcher matcher = Reggie.cached("user-search-pattern", userPattern);

// Check cache status
System.out.println("Cached patterns: " + Reggie.cacheSize());
System.out.println("Keys: " + Reggie.cachedPatterns());

// Clear cache (e.g., on configuration reload)
Reggie.clearCache();

Error Handling

try {
    ReggieMatcher matcher = Reggie.compile("[invalid");
} catch (java.util.regex.PatternSyntaxException e) {
    System.err.println("Invalid pattern: " + e.getMessage());
}

Performance Tips

// ✅ GOOD: Compile once, reuse many times
ReggieMatcher phone = Reggie.compile("\\d{3}-\\d{3}-\\d{4}");
for (String input : inputs) {
    if (phone.matches(input)) {
        // process
    }
}

// ❌ BAD: Don't compile in loops
for (String input : inputs) {
    ReggieMatcher phone = Reggie.compile("\\d{3}-\\d{3}-\\d{4}");  // Cached but wasteful
    if (phone.matches(input)) {
        // process
    }
}

Compile-Time Patterns

The compile-time API generates specialized matchers during build for zero runtime overhead.

Step-by-Step Setup

1. Create Pattern Provider Class

Create an abstract class implementing ReggiePatterns with abstract methods annotated with @RegexPattern:

package com.example.patterns;

import com.datadoghq.reggie.ReggiePatterns;
import com.datadoghq.reggie.annotations.RegexPattern;
import com.datadoghq.reggie.runtime.ReggieMatcher;

public abstract class ValidationPatterns implements ReggiePatterns {

    // Simple patterns
    @RegexPattern("\\d+")
    public abstract ReggieMatcher digits();

    @RegexPattern("[a-zA-Z]+")
    public abstract ReggieMatcher letters();

    // Real-world patterns
    @RegexPattern("\\d{3}-\\d{3}-\\d{4}")
    public abstract ReggieMatcher usPhone();

    @RegexPattern("[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}")
    public abstract ReggieMatcher email();

    @RegexPattern("(?=.*[A-Z])(?=.*\\d)(?=.*[!@#$%]).{8,}")
    public abstract ReggieMatcher strongPassword();
}

2. Build Your Project

The annotation processor runs automatically during compilation:

./gradlew build

Generated files (in build/generated/sources/annotationProcessor):

ValidationPatterns$Impl.java - Implementation of your pattern provider
Individual matcher classes for each pattern

3. Use the Patterns

import com.datadoghq.reggie.Reggie;
import com.example.patterns.ValidationPatterns;

public class Validator {
    // Singleton pattern (optional but recommended)
    private static final ValidationPatterns PATTERNS =
        Reggie.patterns(ValidationPatterns.class);

    public boolean isValidEmail(String email) {
        return PATTERNS.email().matches(email);
    }

    public boolean isStrongPassword(String password) {
        return PATTERNS.strongPassword().matches(password);
    }

    public boolean hasDigits(String text) {
        return PATTERNS.digits().find(text);
    }
}

Pattern Organization

You can organize patterns into multiple classes:

// NetworkPatterns.java
public abstract class NetworkPatterns implements ReggiePatterns {
    @RegexPattern("\\b(?:[0-9]{1,3}\\.){3}[0-9]{1,3}\\b")
    public abstract ReggieMatcher ipv4();

    @RegexPattern("([0-9a-fA-F]{1,4}:){7}[0-9a-fA-F]{1,4}")
    public abstract ReggieMatcher ipv6();
}

// FilePatterns.java
public abstract class FilePatterns implements ReggiePatterns {
    @RegexPattern(".*\\.java$")
    public abstract ReggieMatcher javaFile();

    @RegexPattern(".*\\.(jpg|png|gif)$")
    public abstract ReggieMatcher imageFile();
}

// Usage
NetworkPatterns net = Reggie.patterns(NetworkPatterns.class);
FilePatterns files = Reggie.patterns(FilePatterns.class);

if (net.ipv4().matches(address)) { /* ... */ }
if (files.javaFile().matches(filename)) { /* ... */ }

Compile-Time Error Detection

Invalid patterns are caught at build time:

@RegexPattern("[invalid")  // Missing closing bracket
public abstract ReggieMatcher broken();

// Build output:
// error: Invalid regex pattern: Unclosed character class near index 7
//        [invalid
//                ^

IDE Integration

Modern IDEs (IntelliJ IDEA, VS Code with Java extensions) automatically run annotation processors:

IntelliJ IDEA: Enable "Annotation Processing" in Settings
VS Code: Works automatically with Java extension pack
Eclipse: Enable "Annotation Processing" in project properties

Choosing the Right Approach

Use Case	Recommended	Why
Known patterns in hot paths	Compile-Time	Zero overhead, compile-time validation
User-provided search	Runtime	Dynamic pattern support
Configuration-driven patterns	Runtime	Flexibility to change patterns
Form validation	Compile-Time	Patterns known at build time
Log parsing (fixed formats)	Compile-Time	Maximum performance
Log parsing (user filters)	Runtime	User can customize
GraalVM native-image	Compile-Time	No runtime bytecode generation

General Rule: Use compile-time for static patterns (95% of use cases), runtime for dynamic patterns.

API Reference

Runtime API

`Reggie` Class

// Compile pattern with automatic caching
public static ReggieMatcher compile(String pattern)

// Compile with explicit cache key
public static ReggieMatcher cached(String key, String pattern)

// Cache management
public static void clearCache()
public static int cacheSize()
public static Set<String> cachedPatterns()

`ReggieMatcher` Class

// Test if entire string matches
public abstract boolean matches(String input)

// Find pattern anywhere in string
public abstract boolean find(String input)

// Find pattern starting at position
public abstract int findFrom(String input, int start)
// Returns: start position of match, or -1 if not found

// Get the pattern string
public final String pattern()

Compile-Time API

`@RegexPattern` Annotation

@Retention(RetentionPolicy.SOURCE)
@Target(ElementType.METHOD)
public @interface RegexPattern {
    String value();  // The regex pattern
    ReggieOption[] options() default {};  // Compilation flags (e.g. ALLOW_JDK_FALLBACK)
}

Requirements:

Applied to abstract methods
Method must return ReggieMatcher
Method must take no parameters
Containing class must be abstract and implement ReggiePatterns

`Reggie.patterns()` Method

public static <T extends ReggiePatterns> T patterns(Class<T> patternClass)

Returns an instance of the generated implementation class.

Supported Features

PCRE Compatibility: 115/123 test cases pass (3 fail, 5 error) on a curated common-patterns suite — email/URL/IP/phone/JSON-style patterns; see CorrectnessTest.testCommonPatterns. On the full 364-entry PCRE conformance corpus (CorrectnessTest.testPCRECapturingGroups), Reggie passes 98.1% of the 262 cases it can evaluate; the remaining 102 entries use PCRE features not yet implemented (see PCRE Conformance Roadmap).

✅ Fully Supported

Character classes: [abc], [a-z], [^abc], [a-zA-Z0-9]
Predefined classes: \d, \w, \s (and negated: \D, \W, \S)
Quantifiers: *, +, ?, {n}, {n,}, {n,m}
- Whitespace inside quantifiers: { 3, 5 }, { 3 } (PCRE compatible)
Escape sequences:
- Basic: \n, \t, \r, \\, \/
- Octal: \0100 (octal 100 = '@'), \0377; \1-\9 start a backreference, as in java.util.regex
- Hex: \x40 (hex 40 = '@'), \xFF
Alternation: |
Groups:
- Capturing: (...)
- Non-capturing: (?:...)
- Named groups: (?<name>...), including extraction by name
- Non-capturing branch reset (numbered): (?|(...)|(...))
- Atomic groups: (?>...)
Anchors:
- Line: ^, $
- String: \A (absolute start), \Z (end before optional newline)
- Word: \b (word boundary), \B (non-word boundary)
Lookahead: (?=...), (?!...) (positive/negative)
Lookbehind: (?<=...), (?<!...) (positive/negative)
Inline modifiers:
- Case-insensitive: (?i)
- Dotall mode: (?s) - . matches newlines
- Multiline: (?m)
- Extended: (?x) - ignore whitespace and comments
- Scoped: (?i:...) - modifier applies only inside the group
Quantifiers: greedy, non-greedy (*?, +?, ??), possessive (*+, ++, ?+)
Unicode: \p{L}, \p{N}, and their negations \P{L}, \P{N} (script-based forms like \p{Script=Greek} are not yet supported)
Backreferences: \1, \2, etc., including self-referencing backrefs within a single group ((a\1?){4}), with limitations - see below
Subroutine calls: (?1), (?R) for non-self-embedding references (calls that don't recurse into themselves); self-embedding/context-free recursion is a permanent limitation - see below

🚧 Partial Support / Limitations

Capturing group extraction: Basic support for fixed-width patterns
- Works: (abc)\1 matches "abcabc"
- Limited: Variable-width patterns with quantifiers require backtracking
Backreferences: Supported with limitations
- Fixed quantifiers work: (a{2})\1 matches "aaaa"
- Variable quantifiers have limitations: (a+)\1 matches minimal cases only
- Specialized patterns optimized: <(\w+)>.*</\1> (HTML tags)
Non-greedy quantifiers: *?, +?, ??
- Basic support, complex interactions with lookahead/backref limited
Conditional patterns: (?(condition)yes|no) - basic cases work; combining a conditional with a backref inside a repeated group ((a(?(1)\1)){4}) is a known bug, not yet fixed

❌ Not Yet Supported

Permanent limitation (would require unbounded backtracking to support - see PCRE Conformance Roadmap):

Self-embedding recursive subroutines: (?1)/(?R) calls that recurse into their own group, e.g. palindrome patterns like ^((.)(?1)\2|.?)$
Backtracking control verbs: (*MARK), (*PRUNE), (*SKIP), (*THEN)

Not yet implemented (ordinary backlog, no architecture change needed):

Branch reset groups with named captures: (?|(?'a'aaa)|(?'a'b)) - the numbered form works
Relative backreferences: (?-2), (?+1)
Unicode script/name properties: \p{Script=Greek}, \p{Name=...}

Recent Improvements

✅ Whitespace in quantifiers (PCRE compatible)
✅ Octal escape sequences (\0100, \0377)
✅ Hex escape sequences (\x40, \xFF)
✅ Dotall mode (?s) - dot matches newlines
✅ Absolute string anchors \A and \Z
✅ Possessive quantifiers, atomic groups, Unicode \p{L}/\p{N}, scoped inline modifiers, named group extraction, self-referencing backrefs

See PCRE Conformance Roadmap for detailed compatibility status.

How It Works

Pattern Analysis & Strategy Selection

Reggie analyzes each pattern and selects the optimal matching strategy:

Pattern Analysis Decision Tree:
│
├─ Has backreferences? ───────────────────────► Thompson NFA (bytecode)
│
├─ Has lookahead/lookbehind? ─────────────────► Hybrid DFA+NFA (bytecode)
│
├─ Pure regular (no extended features)?
│  │
│  ├─ Simple pattern (<50 states)? ──────────► Pure DFA Unrolled (bytecode)
│  │
│  ├─ Medium complexity (50-500 states)? ────► Pure DFA Switch (bytecode)
│  │
│  └─ Complex pattern (>500 states)? ────────► Thompson NFA (bytecode)
│
└─ Unsupported features? ─────────────────────► Compile-time error

Beyond this top-level routing, some structural shapes get a dedicated fast path instead of a general-purpose engine. For example, BITSTATE_BYTECODE recognizes patterns of the form ^(?:leadingWs(kw1|kw2|...)separatorWs)?mandatoryCharSet+trailingWs*(tail) (an optional prefix keyword plus a mandatory scan and tail — e.g. shell-command-style patterns) and compiles them to straight-line, non-backtracking bytecode rather than routing through the general BITSTATE_CAPTURE interpreter. See doc/2026-07-08-bitstate-bytecode-generator-design.md for the design rationale.

Generated Code Examples

Literal Pattern (`hello`)

Generated matcher:

public boolean matches(String input) {
    return input != null && input.equals("hello");
}

public boolean find(String input) {
    return input != null && input.contains("hello");
}

Phone Number (`\d{3}-\d{3}-\d{4}`)

Generated matcher (simplified):

public boolean matches(String input) {
    if (input == null || input.length() != 12) return false;
    int pos = 0;

    // Check 3 digits
    for (int i = 0; i < 3; i++) {
        if (!Character.isDigit(input.charAt(pos++))) return false;
    }

    // Check dash
    if (input.charAt(pos++) != '-') return false;

    // Check 3 digits
    for (int i = 0; i < 3; i++) {
        if (!Character.isDigit(input.charAt(pos++))) return false;
    }

    // Check dash
    if (input.charAt(pos++) != '-') return false;

    // Check 4 digits
    for (int i = 0; i < 4; i++) {
        if (!Character.isDigit(input.charAt(pos++))) return false;
    }

    return pos == input.length();
}

Complex Pattern (DFA with Switch)

For patterns with multiple states, generates switch-based DFA:

public boolean matches(String input) {
    if (input == null) return false;
    int state = 0;  // Initial state

    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        switch (state) {
            case 0: state = transition0(c); break;
            case 1: state = transition1(c); break;
            // ... more states
            case -1: return false;  // Error state
        }
    }

    return isAcceptState(state);
}

Architecture Overview

┌─────────────────────────────────────────────────────┐
│                    Reggie API                        │
│  ┌──────────────┐              ┌─────────────────┐  │
│  │ Compile-Time │              │    Runtime      │  │
│  │   Patterns   │              │    Patterns     │  │
│  │ @RegexPattern│              │ Reggie.compile()│  │
│  └──────┬───────┘              └────────┬────────┘  │
└─────────┼──────────────────────────────┼───────────┘
          │                              │
          │                              │
    ┌─────▼─────────┐            ┌───────▼──────────┐
    │  Annotation   │            │     Runtime      │
    │  Processor    │            │    Compiler      │
    │ (Build Time)  │            │  (First Use)     │
    └───────┬───────┘            └────────┬─────────┘
            │                             │
            └──────────┬──────────────────┘
                       │
            ┌──────────▼──────────┐
            │   Shared Codegen    │
            │  ┌──────────────┐   │
            │  │ AST Parser   │   │
            │  │ NFA Builder  │   │
            │  │ DFA Builder  │   │
            │  │ Bytecode Gen │   │
            │  └──────────────┘   │
            └─────────────────────┘
                       │
            ┌──────────▼──────────┐
            │  Generated Matcher  │
            │    (Bytecode)       │
            └─────────────────────┘

Project Structure

reggie/
├── reggie-annotations/     # @RegexPattern annotation definition
├── reggie-codegen/         # Shared bytecode generation (AST, NFA, DFA, codegen)
├── reggie-processor/       # Annotation processor (compile-time path)
├── reggie-runtime/         # Runtime API + interfaces
├── reggie-benchmark/       # Performance benchmarks and examples
├── reggie-integration-tests/ # PCRE/RE2 conformance test suites
└── doc/                    # Documentation and research notes

Design Principle: The reggie-codegen module contains all pattern analysis and bytecode generation logic, shared by both the annotation processor (compile-time) and runtime compiler. This eliminates code duplication and ensures consistent behavior.

Building from Source

Requirements

Java 21+
Gradle 8.11+

Build Commands

# Clone repository
git clone https://github.com/DataDog/java-reggie.git
cd java-reggie

# Build all modules
./gradlew build

# Run tests
./gradlew test

# Run benchmarks
./gradlew :reggie-benchmark:run

# Run JMH benchmarks
./gradlew :reggie-benchmark:jmh

# Clean build
./gradlew clean build

Running Examples

# Simple matcher tests with performance comparison
./gradlew :reggie-benchmark:run

# Expected output:
# Testing generated matchers...
#
# === Phone Matcher ===
# Phone Matcher: PASSED
#
# === Hello Matcher ===
# Hello Matcher: PASSED
#
# === Performance Comparison ===
# Reggie matcher: <N> ms
# JDK Pattern:    <N> ms
# Speedup:        <N>x
#
# Actual timings and speedup vary by hardware and JVM; see the Performance
# section above and run `./gradlew :reggie-benchmark:benchmarkAndReport` for
# a current, trustworthy comparison.

Research & References

Reggie is based on decades of regex engine research:

Regular Expression Matching Can Be Simple And Fast - Russ Cox (2007)
- Thompson's NFA construction algorithm
- Linear-time matching without backtracking
RE2: Google's linear-time regex engine
- Production-proven DFA/NFA hybrid approach
- Guaranteed linear-time performance
.NET Regex Source Generators (.NET 7+)
- Compile-time regex generation (proves concept viability)
Needle: DFA-based regex with bytecode compilation
- Java bytecode generation for regex matchers
PCRE (Perl Compatible Regular Expressions)
- Industry-standard regex compatibility target
- Reggie passes 98.1% of the evaluable cases in the 364-entry PCRE conformance corpus

Novel Contributions

Based on extensive research, Reggie's hybrid compile-time/runtime approach is novel in the Java ecosystem:

No existing annotation-based compile-time regex generators for Java
Combines .NET's source generation concept with Java annotation processing
Unified codegen for both compile-time and runtime paths
Industry-proven hybrid DFA/NFA strategy
High PCRE compatibility (98.1% of evaluable corpus cases) without exponential backtracking

Known Limitations

Complexity limits

Linear time holds per call. Iterating m matches over one input can cost O(n · m) on the DFA strategies.
Backreferences, lookaround, atomic groups, possessive quantifiers, conditionals and recursion have no linear-time guarantee. On the memoized backtracker they are polynomial and capped by step budgets². A lookahead whose DFA has more than 64 states keeps an O(n²) find on the DFA strategies.

See "Performance known gaps" in doc/agents-fallback-and-limitations.md.

Known correctness gaps on adversarial degenerate inputs

The differential fuzzer (AlgorithmicFuzzTest.divergenceGate) tracks 28 pre-existing divergences between Reggie and JDK on adversarial degenerate inputs:

Span-only (group boundaries wrong, boolean match correct): group-span gaps in DFA_UNROLLED_WITH_GROUPS and SPECIALIZED_CONCAT_GREEDY_GROUP.
Boolean correctness (false positives or false negatives on adversarial inputs): OPTIMIZED_NFA_WITH_BACKREFS; \A anchor enforcement in DFA_SWITCH; backref/anchor-combo patterns.

These gaps affect adversarial or synthetically generated patterns; typical production patterns are unlikely to trigger them. The budget ratchets down as each root-cause class is fixed (-Dreggie.fuzz.maxFindings=N overrides the gate; see doc/agents-fallback-and-limitations.md for the authoritative, currently-maintained breakdown).

Contributing

Reggie is production-ready. Contributions are welcome!

Areas for Contribution

Performance optimization: Improve generated code quality
Feature implementation: Capturing groups, backreferences
Benchmark suite: More comprehensive performance tests
Documentation: Tutorials, examples, use cases
Testing: Edge cases, correctness validation

Development Setup

Fork the repository
Create a feature branch: git checkout -b feature/my-feature
Make your changes with tests
Run tests: ./gradlew test
Submit a pull request

See CONTRIBUTING.md for detailed guidelines.

Maintainer

Jaroslav Bachořík (@jbachorik) Email: jaroslav.bachorik@datadoghq.com

For security issues, please see SECURITY.md.

License

Apache License 2.0 - see LICENSE file for details

Acknowledgments

Russ Cox for foundational regex research
Google for RE2
The Java community for ASM library and annotation processing
.NET team for proving source generation viability

Author: Jaroslav Bachorik

Questions? Open an issue on GitHub

Name		Name	Last commit message	Last commit date
.github		.github
.knowledgebase		.knowledgebase
.sphinx		.sphinx
doc		doc
docs		docs
gradle		gradle
reggie-annotations		reggie-annotations
reggie-benchmark		reggie-benchmark
reggie-codegen		reggie-codegen
reggie-integration-tests		reggie-integration-tests
reggie-processor		reggie-processor
reggie-runtime		reggie-runtime
scripts		scripts
.gitignore		.gitignore
.gitlab-ci.yml		.gitlab-ci.yml
AGENTS.md		AGENTS.md
CHANGELOG.md		CHANGELOG.md
CLAUDE.md		CLAUDE.md
CONTRIBUTING.md		CONTRIBUTING.md
LICENSE		LICENSE
LICENSE-3rdparty.csv		LICENSE-3rdparty.csv
NOTICE		NOTICE
README.md		README.md
SECURITY.md		SECURITY.md
analyze-group-failures.py		analyze-group-failures.py
analyze-pcre-gaps.py		analyze-pcre-gaps.py
build.gradle		build.gradle
codecov.yml		codecov.yml
gradle.properties		gradle.properties
gradlew		gradlew
gradlew.bat		gradlew.bat
settings.gradle		settings.gradle

Latest commit

History

Folders and files

Repository files navigation

Reggie - Hybrid Compile-Time and Runtime Optimized Regex for Java

Table of Contents

Why Reggie?

Quick Start

Runtime API (Simplest)

Compile-Time API (Zero Overhead)

Performance

Full Report

Why So Fast?

Engine Comparison

Performance Tuning

Optional: Enable Zero-Copy String Access

How It Works

When Zero-Copy Matters Most

Adding the JVM Argument

Verification

Installation

Gradle

Maven

Complete Usage Guide

Runtime Patterns

Basic Usage

Cache Management

Error Handling

Performance Tips

Compile-Time Patterns

Step-by-Step Setup

Pattern Organization

Compile-Time Error Detection

IDE Integration

Choosing the Right Approach

API Reference

Runtime API

Reggie Class

ReggieMatcher Class

Compile-Time API

@RegexPattern Annotation

Reggie.patterns() Method

Supported Features

✅ Fully Supported

🚧 Partial Support / Limitations

❌ Not Yet Supported

Recent Improvements

How It Works

Pattern Analysis & Strategy Selection

Generated Code Examples

Literal Pattern (hello)

Phone Number (\d{3}-\d{3}-\d{4})

Complex Pattern (DFA with Switch)

Architecture Overview

Project Structure

Building from Source

Requirements

Build Commands

Running Examples

Research & References

Novel Contributions

Known Limitations

Complexity limits

Known correctness gaps on adversarial degenerate inputs

Contributing

Areas for Contribution

Development Setup

Maintainer

License

Acknowledgments

About

Resources

Contributing

Security policy

Stars

Watchers

Forks

Releases

Packages

Used by

`Reggie` Class

`ReggieMatcher` Class

`@RegexPattern` Annotation

`Reggie.patterns()` Method

Literal Pattern (`hello`)

Phone Number (`\d{3}-\d{3}-\d{4}`)