Metadata-Version: 2.4
Name: regexbench
Version: 0.3.0
Summary: Evaluate generated regular expressions: semantic equivalence, correctness, and ReDoS safety.
Project-URL: Homepage, https://github.com/foothills-labs/regexbench
Project-URL: Repository, https://github.com/foothills-labs/regexbench
Project-URL: Issues, https://github.com/foothills-labs/regexbench/issues
Project-URL: Documentation, https://github.com/foothills-labs/regexbench/blob/main/docs/benchmarks.md
Project-URL: Changelog, https://github.com/foothills-labs/regexbench/blob/main/CHANGELOG.md
Author: Foothills Labs
License-Expression: Apache-2.0
License-File: LICENSE
Keywords: automata,benchmark,evaluation,llm,redos,regex
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Classifier: Topic :: Security
Classifier: Topic :: Text Processing
Classifier: Typing :: Typed
Requires-Python: >=3.10
Provides-Extra: dev
Requires-Dist: pytest>=8.0; extra == 'dev'
Requires-Dist: ruff>=0.6; extra == 'dev'
Description-Content-Type: text/markdown

# regexbench

**Evaluate a regex the way a benchmark should.**

Scoring generated regular expressions by string comparison is wrong: `(ab)+`
and `ab(ab)*` are the same language and different strings. And a pattern that
passes every test can still hang a production server.

`regexbench` answers the three questions that actually matter — is it the same
language, does it behave, and is it safe to run.

## Semantic equivalence

Both patterns compile to DFAs and the automata are compared, which is the
DFA-EQ metric used in the regex generation literature.

```python
from regexbench import equivalent

bool(equivalent(r"(ab)+", r"ab(ab)*"))      # True
bool(equivalent(r"[0-9]+", r"[0-9][0-9]*"))  # True

result = equivalent(r"a+", r"a*")
result.verdict     # <Verdict.DIFFERENT>
result.witness     # '' — the shortest string telling them apart
```

Witnesses are shortest-first and real: every one is a string you can paste
into `re.fullmatch` to see the difference yourself.

**When it says it doesn't know.** Backreferences make a pattern non-regular,
and equivalence is then formally undecidable. Rather than guess, the verdict is
`UNDECIDABLE`:

```python
equivalent(r"(a)\1", r"aa").verdict     # <Verdict.UNDECIDABLE>
equivalent(r"(?=a)ab", r"ab").verdict   # <Verdict.UNSUPPORTED>
```

The two are kept apart on purpose. Lookaround *is* regular — it only escapes
the regular languages when combined with backreferences — so refusing it is a
statement about this engine, not about the problem. `UNDECIDABLE` means nothing
can answer; `UNSUPPORTED` means this does not.

**Shorthand classes follow `re`, which means Unicode.** `\d` matches every
Unicode digit, so it is not `[0-9]`:

```python
equivalent(r"\d", "[0-9]").verdict     # <Verdict.DIFFERENT>
equivalent(r"\d", "[0-9]").witness     # '٣'
```

That is pedantic and it is also what `re` does — and `check()` runs the real
`re`, so an engine that called them equivalent would contradict the tool it
lives in.

## Match semantics

Equivalence and scoring default to **full matches**, like `re.fullmatch`. Not
every benchmark means that, and the disagreement is silent — a reference
written for `re.search` simply looks wrong when full-matched.

```python
from regexbench import Semantics, equivalent

equivalent("a", ".*a.*").verdict                              # DIFFERENT
equivalent("a", ".*a.*", semantics=Semantics.SEARCH).verdict  # EQUIVALENT
```

Under `SEARCH`, `p` is rewritten to `.*p.*` around whatever it already
anchors, so there is still exactly one notion of equivalence underneath. The
wildcards distribute over a top-level alternation, because in `a|b$` the
anchor constrains `b` and says nothing about `a`.

Measured on Re(gEx|DoS)Eval: its reference expressions pass **100%** of their
own tests under `search` and **94.0%** under `fullmatch`. Choosing wrong there
would score 46 gold patterns as failing the tests they were written for.

## Dialects

The natural-language-to-regex corpora are not written in Python syntax. They
use `dk.brics.automaton` notation, where `&` is intersection and `~` is
complement — and Python's `re` compiles both as ordinary literals without
complaint.

```python
from regexbench import Dialect, equivalent

# In Python this is the literal "a&b". In dk.brics it is the empty language.
equivalent("(a)&(b)", r"a\&b").verdict                        # EQUIVALENT
equivalent("(a)&(b)", r"a\&b", dialect=Dialect.BRICS).verdict # DIFFERENT

equivalent("([0-9])&([0-4])", "[0-4]", dialect=Dialect.BRICS).verdict  # EQUIVALENT
```

`&` appears in 22.8% of KB13 and 27.3% of NL-RX, `~` in 7.6% and 17.2%. The
dialect is never sniffed, because both readings compile and only one is right.

The grammar follows
[dk.brics.automaton](https://www.brics.dk/automaton/doc/dk/brics/automaton/RegExp.html)
exactly, including precedence — union binds loosest, then intersection, then
concatenation, then repetition, then complement. Note that equivalence with
*both* complement and intersection is
[non-elementary](https://www.cs.umd.edu/~gasarch/TOPICS/desc/regexpcompint.pdf),
not merely PSPACE-complete: deeply nested `&`/`~` is refused with
`UNSUPPORTED` once determinization passes a state budget, rather than run until
the machine gives up.

## ReDoS safety

Two passes. Structural analysis finds the shapes that backtrack
catastrophically and says *why*; an empirical pass then runs the pattern
against attack strings under a timeout to catch what the structural pass
doesn't model.

```python
from regexbench import screen

screen(r"(a+)+").risk        # <Risk.EXPONENTIAL>
screen(r"(a+)+").reason      # 'a quantifier wraps a quantified group...'
screen(r"\d{3}-\d{4}").risk  # <Risk.SAFE>
```

`SAFE` means "no known-bad shape and no blow-up on what we tried". That is a
screening result, not a proof.

The structural pass covers three of the five vulnerability families named in
[the ICPC 2024 study of LLM-generated regexes](https://dl.acm.org/doi/10.1145/3643916.3644424):
nested quantifiers, exponential overlapping disjunction, and polynomial
overlapping adjacency. Exponential overlapping adjacency and starting-with-large-quantifier
are not modelled structurally and are only caught when the empirical pass
happens to trip them. That study also found LLM-generated regexes skew toward
*polynomial* ReDoS — the cheaper family to miss, and the one a short attack
string is least likely to expose.

## Running untrusted patterns

Python's `re` has no timeout, and a pathological pattern spins inside a single
C call that no signal or thread can interrupt. The only reliable escape is a
separate process:

```python
from regexbench import safe_search, MatchTimeout

try:
    safe_search(r"(a+)+$", "a" * 40 + "!", timeout=0.5)
except MatchTimeout:
    ...   # the process was killed; your server is still up
```

Costs milliseconds per call. Use it for model output and user input; use `re`
directly for patterns you wrote.

## Scoring against examples

```python
from regexbench import Task, evaluate

task = Task(
    prompt="three digits, a hyphen, four digits",
    positives=["123-4567"],
    negatives=["123-456", "abc"],
    reference=r"[0-9]{3}-[0-9]{4}",
)

report = evaluate(r"[0-9][0-9][0-9]-[0-9]{4}", task)
report.correctness.accuracy   # 1.0
report.equivalence.verdict    # <Verdict.EQUIVALENT>
report.usable                 # True — correct *and* safe
```

`usable` is the one to gate on: never a ReDoS liability, never *proven*
different from the reference, and perfect on whatever examples exist. A pattern
that passes every example it was given can still be known-wrong —
`#[0-9a-f]{6}` passes a hex-colour task whose examples happen to be lowercase —
and the reference settles it.

## Benchmarks

Scores are comparable only when they are computed on the same problems, so
loaders are included for the corpora this literature reports on. No dataset is
redistributed; you download the files and pass the path.

```python
from regexbench.datasets import load_regexeval, load_deep_regex, load_tasks

tasks = load_regexeval("RegexEval.json")      # 762 real prompts, with tests
tasks = load_deep_regex("datasets/KB13")      # 824 gold patterns, no examples
tasks = load_tasks("my_eval.jsonl")           # your own
```

Each loader sets the semantics and dialect the corpus actually uses. Loaders
never filter: a record this engine cannot represent is still returned and
surfaces as `UNSUPPORTED` when scored, because a corpus quietly reduced to its
easy half reports a number nobody can interpret.

See [docs/benchmarks.md](docs/benchmarks.md) for where to download each one and
what coverage to expect.

## Scoring a whole model

```python
from regexbench import run

report = run(tasks, predictions, name="my-model", workers=8)
print(report.table(ks=(1, 5)))
```

```
my-model
762 tasks, 762 answered
  pass@1               77.0%
  dfa-eq@1             56.2%  (whole corpus — a lower bound)
  dfa-eq@1 (decided)   74.9%  (engine limits excluded — model only)
  exact@1              55.4%
  usable@1             65.4%
  vulnerable@1         12.1%  (lower is better)
  180 task(s) undecidable — counted against dfa-eq, excluded from dfa-eq (decided)
```

`predictions` is a mapping from task name to the pattern, or to a list of
sampled patterns, or a sequence aligned with the tasks. All metrics use the
unbiased pass@k estimator, so they line up with published numbers.

**A metric no task can answer is `None`, not zero** — KB13 ships no examples,
and a 0% pass@1 would read as a model failing a question nobody asked it.

**`dfa-eq` is reported twice**, because one number cannot answer both honest
questions. The plain figure counts undecidable comparisons as failures: how
much of the corpus was *verified* correct, a lower bound that cannot flatter.
The `(decided)` figure drops those tasks from the denominator: how much of what
could be checked was correct, the model alone. On KB13 the gold answers
themselves score 51.1% and 100.0% — a 49-point spread that is not a model
result at all, but the `\b` gap in this engine.

## CLI

```bash
regexbench eq '[0-9]+' '[0-9][0-9]*'        # equivalent
regexbench eq --search 'a' '.*a.*'          # equivalent
regexbench eq --brics '([0-9])&([0-4])' '[0-4]'
regexbench safety '(a+)+'                   # exponential
regexbench check '\d{3}' task.json          # 5/5 (100%)

regexbench run regexeval RegexEval.json --predictions preds.json --k 1 5
```

Exit codes are meaningful, so these compose in CI: `0` on equivalent/safe/all
passing, `1` otherwise.

`run` also takes `--use-reference`, which scores every task against its own
gold answer. That sounds circular and is the cheapest sanity check available:
if `pass@1` comes back well below 100%, the dataset is loaded with the wrong
match semantics and every later number is meaningless.

## Supported syntax

The equivalence engine covers the genuinely regular subset: literals, escapes
(`\d \w \s` and negations, plus `\xHH`, `\uHHHH`, `\UHHHHHHHH`, `\N{NAME}`,
`\a` and octal), `.`, character classes with ranges and negation, `*` `+` `?`
`{m,n}`, alternation, and grouping. In the `BRICS` dialect it also
covers intersection (`&`), complement (`~`), any-string (`@`) and the empty
language (`#`) — all regular operations, computed on the automata directly.
Anything else returns `UNSUPPORTED` or `UNDECIDABLE` rather than a wrong
answer.

Anchors are resolved wherever they appear, not just at the ends. Under
full-match semantics `^` can only hold where everything before it is empty, so
`a^` is the empty language, `a?^c` is `c`, and `(^a)*` is `a?` — the same
strings Python matches. Under `SEARCH` semantics an anchor away from the ends
is refused instead: the `.*p.*` rewrite cannot express it.

Patterns Python's own parser rejects are rejected here too — `a**`, `\b*`,
`\q`, `[\d-z]`. A pattern that cannot run under `re` should not get a verdict
from a tool whose correctness and ReDoS halves both run `re`.

Word boundaries (`\b`, `\B`) are supported. They look like lookaround and are
not: the condition depends only on the two characters either side of a
position, so a finite automaton can carry it in one bit of state. Deciding it
does require the alphabet to tell word characters from the rest, which is why
"every other character" is two symbols here rather than one.

In the dk.brics dialect this is a deliberate deviation from the spec, which
escapes `\b` to the literal character `b`. The corpora mean a boundary and
their paired descriptions say so — KB13 glosses `.*\b[A-Za-z]*er\b.*` as "lines
using words ending in 'er'", which the literal reading does not describe.

`\B` follows Python rather than mathematics: it is `¬\b` everywhere except the
empty string, which `re` refuses even though no boundary exists there. Patterns
scored here are run by `re`, so `re` is what gets modelled.

## Install

```bash
pip install regexbench
```

Python 3.10+. **No runtime dependencies** — stdlib only, deliberately, so this
drops into a training or CI pipeline without dragging anything with it.

## Status

Alpha: the API will change, and the version is 0.x for that reason. What is
stable is the discipline — every number in this README and in
[docs/benchmarks.md](docs/benchmarks.md) came from a run, and the equivalence
engine is differential-tested against Python's own `re` on every release.

Known limits, in the order they cost you coverage:

| Construct | Status |
| --- | --- |
| Lookaround | `UNSUPPORTED` — regular, not built. 5.6% of Re(gEx|DoS)Eval |
| Backreferences | `UNDECIDABLE` — no engine can answer this |
| `[\D0-9]` — a negated shorthand mixed with other members | `UNSUPPORTED` — not one character set |
| Possessive quantifiers, atomic groups | `UNSUPPORTED` unless the body matches exactly one way |

Correctness scoring and ReDoS screening have no such limit — they run the real
`re` engine and work on any pattern it compiles.

## Contributing

See [CONTRIBUTING.md](CONTRIBUTING.md). The short version: a wrong answer is
worse than no answer, so anything the engine cannot decide has to say so.

Changes are listed in [CHANGELOG.md](CHANGELOG.md).

## License

Apache-2.0.
