PHPRegex Architecture

This document explains how PHPRegex works under the hood. It is written for future maintainers and contributors who want to understand the AST, the parsing pipeline, and the analysis algorithms.

Pipeline Overview

PHPRegex treats a regex literal as structured input:

• PatternParser splits the literal into pattern and flags.
• The lexer builds a TokenStream with byte offsets.
• The parser builds a RegexNode AST.
• Visitors walk the AST to validate, explain, analyze, or transform.

Step 1: Parse the Regex Literal

Regex::parse() accepts a full PCRE literal (/pattern/flags). Internally, the literal is split into:

• Pattern body (the text between delimiters)
• Delimiter (the chosen boundary character)
• Flags (i, m, s, u, x, and more)

This happens in PHPRegex\Parser\Internal\PatternParser. The output is then passed to the lexer.

Step 2: Lexer (Tokenization)

src/Parser/Lexer.php scans the pattern body as bytes and emits tokens with start/end offsets. The lexer is stateful because PCRE syntax changes meaning depending on context. The main states include:

• Default text
• Character class ([...])
• Quoted literal blocks (\Q...\E)
• Comment blocks ((?#...))

The lexer output is a TokenStream, which is a linear sequence of Token objects. Tokens are positional, and offsets are byte-based so diagnostics line up with the original string.

Lexer Contexts and Tunnel Modes

The lexer maintains explicit state flags:

• inCharClass switches to the character-class token set until a closing ].
• inQuoteMode treats everything as literal until \E.
• inCommentMode consumes (?# ... ) as literal content until ).

Quote mode is allowed to run to end-of-pattern (PCRE treats \Q without \E as valid). Comment mode and character classes must be closed, or the lexer raises a LexerException in validateFinalState().

Token Priority and Matching

Tokens are matched by compiling two prioritized token maps into a single regex:

• TOKENS_OUTSIDE for normal parsing
• TOKENS_INSIDE for character-class parsing

At each position, the lexer runs the compiled pattern with an anchored match (/A) to find the next token. Context-sensitive literals are adjusted after matching; for example:

• ^ at the start of a class becomes TokenType::Negation
• - within a class becomes TokenType::Range

This keeps lexing fast and deterministic while preserving byte offsets.

Step 3: Parser (Recursive Descent)

src/Parser/Syntax/TokenParser.php is a handwritten recursive descent parser. It walks the TokenStream and builds an AST that reflects PCRE precedence:

• Atoms (literals, classes, groups)
• Quantifiers
• Concatenation (sequence)
• Alternation (|)

The parser entry point is parse(), which delegates to smaller methods such as:

• parseAlternation()
• parseSequence()
• parseQuantifiedAtom()
• parseAtom()

Errors raised here become SyntaxErrorException or SemanticErrorException and include byte offsets for IDE integration.

Parser Precedence and Flow

The parser implements precedence by control flow:

• parseAlternation() splits on | and builds AlternationNode only when multiple branches exist.
• parseSequence() consumes consecutive items until it hits | or ), building a SequenceNode.
• parseQuantifiedAtom() parses one atom, then checks for a trailing quantifier and wraps it in a QuantifierNode.
• parseAtom() delegates to specialized handlers for groups, character classes, verbs, assertions, and literals.

Extended mode (/x) is handled inside parseSequence() via consumeExtendedModeContent(). Whitespace and inline comments become nodes where necessary so the compiler can round-trip the original pattern.

Step 4: AST Structure

Every node:

• Is immutable (readonly)
• Holds startPosition and endPosition byte offsets
• Implements NodeInterface::accept()

The root node is RegexNode, which wraps the parsed pattern and flags.

Example AST shape:

Pattern: /^(?<email>\w+@\w+\.\w+)$/

RegexNode
└── SequenceNode
    ├── AnchorNode("^")
    ├── GroupNode(name: email)
    │   └── SequenceNode
    │       ├── QuantifierNode("+") -> CharTypeNode("\\w")
    │       ├── LiteralNode("@")
    │       ├── QuantifierNode("+") -> CharTypeNode("\\w")
    │       ├── LiteralNode(".")
    │       └── QuantifierNode("+") -> CharTypeNode("\\w")
    └── AnchorNode("$")

Node definitions live in src/Parser/Node/. The full node reference is in docs/nodes/README.md.

Step 5: Visitors and Traversal

Visitors encapsulate behavior. Each node calls the correct method on the visitor, enabling double-dispatch:

$node->accept($visitor)
  -> $visitor->visitXxx($node)

Built-in visitors live in the package that owns their concern, and include:

• Parser\Validation\Validator (src/Parser/Validation/)
• Explain\TextExplainer (src/Explain/)
• Parser\Printer\PatternPrinter (src/Parser/Printer/)
• Redos\RedosProfiler (src/Redos/)
• Optimizer\Rewriter (src/Optimizer/)

Traversal details are in docs/design/ast-traversal.md.

The Normalized Form (HIR)

Next to the AST, HirTranslator (src/Parser/Hir/) builds a second form of a pattern that says what it matches, with the syntax gone:

• options are applied where they hold: a character, a class, a dot or a caseless letter becomes one CharSet, asked from the PCRE2 that runs, so \w under u, \p{L} and k under iu — which also matches the Kelvin sign U+212A — are exact for the running PHP;
• groups that only group are removed: (?:a)|(?:bc) is an alternation of two literals;
• every quantifier is a repetition with its bounds and its greed;
• what PCRE does in order stays in order: alternatives, greed, atomic groups. Backreferences, subroutine calls and verbs stay as opaque nodes.

Each node carries Properties, worked out once when it is built: minimum and maximum length, nullability, the sets of first and last characters, the literal prefix and suffix, the capture count, and whether the node is a regular expression in the textbook sense. An analysis reads them instead of re-deriving them from the AST.

CharSet, ClassSetProvider and Utf8 live here so that every library shares one set of characters and one engine oracle. The automata solver builds its NFA from this form — the first analysis to consume the tree itself — while the ReDoS engine still walks the AST and borrows the primitives (CharSet, ClassSetProvider, Utf8) from this layer. The layer is internal while the analyses move onto it.

Diagnostics and Validation

Validation runs against the AST and produces structured errors. Regex::validate() returns a ValidationResult containing:

• isValid()
• Error message and hint
• Byte offset and caret snippet

Diagnostics codes and explanations are documented in docs/reference/diagnostics.md.

ReDoS Analysis (Static)

ReDoS analysis uses the AST and never executes the regex (unless confirmed mode is asked for). RedosAnalyzer does two things with the tree:

1. It builds a prioritized NFA of PCRE’s backtracking (Redos\Internal\Backtrack): ε-transitions ordered as PCRE tries them, character sets exact (computed from the running PCRE2 under /u and /i), atomic groups, possessive quantifiers and lookaround bodies as separate sub-automata. Ambiguity in that automaton proves the complexity class of one match attempt, linear, polynomial of degree k or exponential, and yields the witness prefix . pump x n . suffix. The work is bounded by RedosOptions, in states and steps.
2. It runs RedosProfiler, the structural heuristics, with a CharSetAnalyzer. They decide when the pattern holds a construct outside the model (backreferences, conditionals, recursion, verbs, callouts) or the model runs out of budget, and they provide the findings, hotspots and recommendations of every result.

RedosAnalysis::$proof says which one decided. Core heuristics include:

• Nested unbounded quantifiers (star height > 1)
• Overlapping alternation branches inside repetition
• Backreference loops within unbounded quantifiers
• Quantifiers that repeat empty-match subpatterns
• Adjacent quantified tokens with overlapping character sets
• Large bounded quantifiers (low risk, but flagged)
• Atomic groups and possessive quantifiers lowering severity

Analysis results are wrapped in RedosAnalysis and include the severity, the complexity class, the proof, the witness, findings and suggested rewrites. See docs/guides/redos.md for user-facing guidance.

ReDoS Heuristics in Practice

RedosProfiler tracks quantifier depth and atomic context while walking the AST:

• unboundedQuantifierDepth and totalQuantifierDepth model star height and nesting.
• Atomic groups ((?>...)) and possessive quantifiers (*+, ++, {m,n}+) toggle inAtomicGroup, which reduces or avoids severity.
• CharSetAnalyzer compares alternation branches to detect overlap inside repetition.
• Backreference loops inside unbounded quantifiers are flagged as high risk.

Findings are collected as Finding objects, and the visitor records a culpritNode and hotspots so the CLI can highlight where the risk originates.

CLI Lint Pipeline

The CLI linter runs in two stages:

1. Extract patterns from files into PatternOccurrence entries.
2. Analyze and format the results into a LintReport (console/json/github).

When --jobs is used and pcntl_fork is available, both extraction and analysis run in parallel workers. Each worker handles a chunk of files or patterns, and the parent process aggregates results.

Layers

The code falls into layers, each allowed to use only those below it, and deptrac checks the rule on every change (composer deptrac):

What reads a pattern below the facade takes a RegexParser; Regex::parser() gives the one a facade uses.

Caching and Limits

PHPRegex can cache ASTs via CacheInterface. By default it keeps the latest 1024 trees in memory (ArrayCache); nothing is written to disk unless a directory is named with cache => '/path' or a FilesystemCache. A filesystem cache stores data, never code, in a directory it creates for its owner only (0700), and ignores a directory another user owns or others can write to. Shared caches go through the PSR-6 and PSR-16 adapters. You can disable caching with cache => null in Regex::create() options.

Limits are enforced in ParserOptions:

• max_pattern_length
• max_lookbehind_length (variable-length lookbehinds; a fixed-length one is only limited by PCRE’s 65535)
• max_recursion_depth
• php_version and pcre_version, resolved once into a PcreTarget that the lexer, the parser, the validator and the cache key read

Extension Points

When you add a new PCRE construct, you typically update:

• src/Parser/Node/* to define a node
• src/Parser/Syntax/TokenParser.php and src/Parser/Lexer.php to recognize syntax
• src/Parser/NodeVisitorInterface.php and every visitor that implements it, to support traversal
• Tests and fixtures for valid/invalid cases

See docs/extending.md for the full workflow.

Edit on GitHub Copy as Markdown