README

PHPRegex Automata

Compiles the regular subset of PCRE to automata to compare languages: equivalence, intersection, subset and example strings.

Features

Equivalence, intersection and subset checks, each answered with the shortest witness or counter-example string, and stamped with the PCRE2 release that answered (pcreVersion)
Patterns compile to DFAs: NFA construction, determinization, then Hopcroft or Moore minimization
Two match semantics: the whole input (MatchMode::Full) or any substring (MatchMode::Partial)
The i, s and u flags, character classes and ranges, dot, ^/$, alternation, groups and quantifiers — and POSIX classes, Unicode properties (\p{...}), Perl extended classes ((?[ ... ])) and \C
Every character set is asked from the PCRE2 that runs in your PHP, so verdicts follow the engine (bytes without /u, code points minus the surrogate block with it)
Lookarounds, (?=...), (?!...), (?<=...) and (?<!...), read as the regular languages they keep: a password rule ^(?=.*\d)(?=.*[a-z]).{8,}$ compares like any pattern
Backreferences, recursion and other non-regular constructs throw a ComplexityException instead of a wrong answer
NFA, DFA and transition budgets bound the work on pathological patterns
A pluggable DFA cache (DfaCacheInterface) reuses compiled automata across questions
compile() exposes the DFA of a single pattern

Installation

composer require php-regex/regex-automata

PHP 8.2 or newer. php-regex/regex-parser is pulled in automatically.

Configuration

Every question takes an optional SolverOptions object as its last argument.

Option	Values	Default
`matchMode`	`MatchMode::Full`, `MatchMode::Partial`	`Full`
`maxNfaStates`	int	`5000`
`maxDfaStates`	int	`10000`
`minimizeDfa`	bool	`true`
`minimizationAlgorithm`	`MinimizationAlgorithm::Hopcroft`, `::Moore`	`Hopcroft`
`determinizationAlgorithm`	`DeterminizationAlgorithm::SubsetIndexed`, `::Subset`	`SubsetIndexed`
`maxTransitionsProcessed`	int, `null` to disable the guard	`1000000`

Reaching a limit throws the same ComplexityException as an unsupported construct. The solver constructor also accepts a DfaCacheInterface (InMemoryDfaCache ships with the package) to reuse compiled DFAs across questions.

Usage

Are two patterns interchangeable? When they are not, the shortest string only one side matches tells you where they differ:

use PHPRegex\Automata\LanguageSolver;

$solver = new LanguageSolver();

$result = $solver->equivalent('/a+/', '/a*a+/');
var_dump($result->isEquivalent); // bool(true)

$result = $solver->equivalent('/\w+/', '/[a-z]+/');
var_dump($result->isEquivalent);     // bool(false)
var_dump($result->leftOnlyExample);  // string(1) "0"
var_dump($result->rightOnlyExample); // NULL

Do two route patterns ever match the same URL?

$result = $solver->intersection('/user\/[a-z0-9_]+/', '/user\/[0-9]+/');

var_dump($result->isEmpty); // bool(false)
echo $result->example;      // user/0

Is every string of one pattern also matched by the other?

var_dump($solver->subsetOf('/\d{3}/', '/\d+/')->isSubset); // bool(true)

$result = $solver->subsetOf('/\d+/', '/\d{3}/');

var_dump($result->isSubset);       // bool(false)
var_dump($result->counterExample); // string(1) "0"

Match semantics change what a pattern means. /a/ alone accepts only the string a; searched anywhere in the input it accepts every string that contains an a:

use PHPRegex\Automata\Options\MatchMode;
use PHPRegex\Automata\Options\SolverOptions;

$options = new SolverOptions(matchMode: MatchMode::Partial);

var_dump($solver->equivalent('/a/', '/^a$/', $options)->isEquivalent); // bool(false)
var_dump($solver->equivalent('/a/', '/^a$/')->isEquivalent);           // bool(true)

Outside the regular subset there is no answer to fake — the exception names the limit:

use PHPRegex\Automata\Exception\ComplexityException;

try {
    $solver->equivalent('/(a)\1/', '/aa/');
} catch (ComplexityException $e) {
    echo $e->getMessage(); // Backreferences, subroutines, callouts and control verbs carry match state the automata solver cannot read as a pure language.
}

Every reason has its own message — conditionals, nested lookarounds, atomic groups, zero-width conditions, unsafe possessives, unsupported flags — listed in the logic solver reference.

Documentation

Logic solver reference — the concept, the route-conflict, security-audit and refactoring use cases, strategy tuning and safety limits
API reference — the solver entry points among the library's public API
Feature support matrix — which constructs every component supports, the solver column included
Correctness contracts — the semantics each solver answer rests on
Backward compatibility promise — what stays stable across releases

This package is part of PHPRegex, released with its siblings under one version number.

Resources

Documentation
The parsing core it builds on: regex-parser
Changelog
Report issues and send pull requests in the main PHPRegex repository

License

MIT. See LICENSE.

php-regex / regex-automata

Package info

Security

Fund package maintenance!

Statistics