Copied from wiki.php.net, last synchronized Nov 6, 2026 13:46 UTC
This RFC proposes adding prepared literal substring matching and replacement to PHP, based on the Aho–Corasick algorithm: Str\Matcher, Str\Replacer, and Str\MatchResult. The new API complements the standard string functions and PCRE, providing an alternative for workloads where preparing a dictionary can make text processing more efficient.
PHP's standard string functions and PCRE handle a wide range of search and replacement tasks well. However, a distinct use case arises with a large, rarely changing dictionary: the same set of literal strings is applied to many texts. This is particularly relevant to long-running workers, where the cost of preparing the dictionary can be amortized across many operations.
Solutions for these tasks already exist in the PHP ecosystem, such as Wikimedia AhoCorasick. However, PHP's standard API does not provide a prepared object for multi-pattern literal matching that can enumerate overlapping occurrences, count them, and return the unique keywords found. For replacement, strtr() is available, but its prepared internal structure is not exposed to applications for reuse.
The proposed classes provide a native implementation with a consistent contract. The benchmark study shows that preparation can pay off not only when processing many texts, but in some cases even for a single call. For other tasks and inputs, the existing functions remain more efficient. No direct comparisons with userland libraries were performed.
The proposal introduces two independent prepared classes, Str\Matcher and Str\Replacer, as well as the result type Str\MatchResult. All three classes are final, and dynamic properties are prohibited. For Matcher, a dictionary is a list of strings to search for; for Replacer, it maps strings to their replacement values.
The author proposes including the functionality in ext/standard, under the Str namespace, as basic string operations. The current prototype is in ext/strmatch; the final integration approach is discussed in Open Issues.
<?php
namespace Str;
final class Matcher
{
/** @param array<array-key, string> $keywords */
public function __construct(array $keywords) {}
public function matches(string $subject): bool {}
public function countMatches(string $subject): int {}
/** @return list<string> */
public function getMatchedKeywords(string $subject): array {}
/** @return list<MatchResult> */
public function matchAll(string $subject): array {}
/** @return list<string> */
public function getKeywords(): array {}
}
final class MatchResult
{
private function __construct() {}
public readonly int $offset;
public readonly int $length;
public readonly string $keyword;
}
A keyword is a non-empty string. Matching is case-sensitive and byte-oriented; keywords are not interpreted as regular expressions.
matches($subject) returns a bool and stops scanning when the first detected match ends. This need not be the match with the earliest start: a shorter keyword may end before a longer keyword that started earlier.countMatches($subject) returns the total number of occurrences, including overlaps and matches of different keywords at the same position, without constructing a list of results.getMatchedKeywords($subject) returns each matched keyword once, ordered by its first occurrence. When matches start at the same offset, the shorter keyword comes first. Once all dictionary keywords have been found, scanning may stop before the end of the text.matchAll($subject) returns all occurrences, including overlapping ones, as MatchResult objects. Results are ordered by start offset, then by increasing length.getKeywords() returns the stored unique keywords in the order of their first appearance in the input list.MatchResult properties are: offset — the zero-based starting byte offset; length — the match length in bytes; and keyword — the matched string. For every result, substr($subject, $match->offset, $match->length) === $match->keyword holds. Strings in the results remain valid after the Matcher is destroyed.
If the number of occurrences exceeds PHP_INT_MAX, the current implementation of countMatches() throws an Error. The final error types are discussed under Open Issues.
<?php
$matcher = new Str\Matcher(['a', 'aa']);
$matcher->matches('aaa'); // true
$matcher->countMatches('aaa'); // 5
$matcher->getMatchedKeywords('aaa'); // ['a', 'aa']
foreach ($matcher->matchAll('aaa') as $match) {
printf("%d:%d:%s\n", $match->offset, $match->length, $match->keyword);
}
0:1:a
0:2:aa
1:1:a
1:2:aa
2:1:a
<?php
namespace Str;
final class Replacer
{
/** @param array<array-key, string> $replacements */
public function __construct(array $replacements) {}
public function replace(string $subject, &$count = null): string {}
/** @return array<array-key, string> */
public function getReplacements(): array {}
}
replace($subject, &$count) performs non-overlapping literal replacements, selecting matches according to the same rules as the array form of strtr(): it chooses the earliest start position, then the longest keyword starting there, and continues scanning after the selected keyword. Inserted replacement text is not processed again. Dictionary order does not give a shorter keyword priority over a longer one.
The optional $count argument is passed by reference and receives the number of replacements actually performed, including replacements with an empty string or the same string. If the argument is omitted, no assignment takes place. The variable may initially contain a value of any type; assignment follows PHP's usual rules for references and typed properties.
getReplacements() returns the stored dictionary without references to the original variables. An empty replacement value removes the matched keyword.
<?php
$replacer = new Str\Replacer(['a' => 'Y', 'aa' => 'X']);
$result = $replacer->replace('aaa', $count);
// $result === 'XY'
// $count === 2
Matcher uses the values of the input array and ignores its keys. Duplicate strings are removed, preserving the first occurrence. Every element must be a string; numbers and Stringable objects are not implicitly converted, even without strict_types. References to string values are allowed.
Replacer uses array keys as the substrings to search for, and array values as replacement strings. Integer PHP array keys are interpreted as their decimal string representations (for example, the key 12 corresponds to the string 12). All replacement values must be strings, with no implicit type conversion; references are allowed.
Empty search strings are prohibited (ValueError); values of invalid types cause a TypeError. Empty dictionaries are allowed: matching methods return false, 0, or an empty list, as appropriate; replace() returns the original string and, if $count is supplied, sets it to 0.
The dictionary is immutable after construction: changing the input array, references within it, or arrays returned by getKeywords()/getReplacements() does not change the object's behavior. To use a different dictionary or replacement values, a new object must be created.
Reinitializing an already prepared object throws an Error, even if its dictionary is empty. A constructor error does not leave a partially initialized object. Matcher and Replacer cannot be cloned or serialized; two distinct objects compare unequal with ==, even if their dictionaries are identical. === uses normal object identity.
MatchResult has a private constructor and readonly properties; direct creation with new Str\MatchResult() is not permitted. Normal PHP rules apply to comparisons based on property values, cloning, and serialization.
Matching and replacement are binary-safe, including null bytes. There is no implicit handling of character encoding, case folding, word boundaries, or Unicode normalization. A valid UTF-8 string is matched as an exact sequence of bytes; offsets and lengths remain byte-based.
<?php
$documents = [
'Read json_encode() and json_decode().',
'Call session_start() before output.',
];
$matcher = new Str\Matcher(['json_encode', 'json_decode', 'session_start']);
$index = [];
foreach ($documents as $id => $document) {
$index[$id] = $matcher->getMatchedKeywords($document);
}
// $index === [['json_encode', 'json_decode'], ['session_start']]
<?php
$documents = [
'See https://old.example.test/help.',
'Visit https://old.example.test.',
];
$replacer = new Str\Replacer([
'https://old.example.test/help' => 'https://new.example.test/support',
'https://old.example.test' => 'https://new.example.test',
]);
foreach ($documents as $id => $document) {
$documents[$id] = $replacer->replace($document);
}
// $documents === [
// 'See https://new.example.test/support.',
// 'Visit https://new.example.test.',
// ]
This is literal replacement, not URL or HTML parsing. The examples demonstrate behavior and reuse; no performance advantage is claimed for these short inputs.
Matching and replacement are separate classes: Matcher enumerates overlapping occurrences, while Replacer applies non-overlapping replacements using leftmost-longest selection and stores replacement values. Separate objects avoid unnecessary data and switches between matching semantics. The getKeywords() and getReplacements() methods provide access to the stored dictionary snapshot without allowing it to be modified.
The Rust ''aho-corasick'' library distinguishes ordinary matching that can report overlaps from non-overlapping match selection modes, including leftmost-longest.
Go's ''strings.NewReplacer'' provides prepared replacement but resolves competing keywords by argument order rather than length. These are examples of API design choices; neither API compatibility nor a performance advantage over these implementations is claimed.
Prepared object (Prepared) measures a method call on an already constructed object, including creation and release of the result.
One-shot call (One-shot) includes constructing the object, calling one method, releasing its result, and destroying the object. Existing methods use prepared arguments and a warmed-up PCRE cache.
The following three cases illustrate why distinguishing these modes matters. Times are in microseconds, GCC 15.2:
| Operation and input | Best existing method | Prepared object | One-shot call |
|---|---|---|---|
getMatchedKeywords(); 1 KiB, 128 keys of 12 B each, one occurrence |
preg_match_all(): 26.284 |
1.144 | 53.538 |
replace(); 4 KiB, 32 keys of 11–21 B, 16 replacements |
preg_replace_callback(): 9.380 |
6.247 | 19.790 |
replace(); 16 KiB, the same dictionary, 16 replacements |
preg_replace_callback(): 62.595 |
26.065 | 40.257 |
The prepared object is faster in all three cases, but one-shot construction pays off only in the third. For Matcher, prepared and one-shot modes were measured in separate series; the displayed alternative time comes from the one-shot series. Exact relative changes are based on paired samples, rather than ratios of the rounded numbers in this table.
The following are selected one-shot calls, including object construction and destruction. The measured implementation at 7c7550bcdac is identical to the one archived in the study at 47e75e5. AMD Ryzen 9 5950X, Linux x86-64; GCC 15.2 / Clang 21.1. Source and binary hashes and build parameters are listed in SOURCE.md.
Each row is compared against the fastest eligible existing method by median elapsed time. The percentage is the median of paired relative changes; negative values mean less time. All comparisons shown passed the quality checks. The study does not classify differences below 2% as wins or losses; this is a reporting convention, not an estimate of uncertainty. replace($subject) was measured without the optional $count argument.
| Operation and exact input | Best measured existing method | One-shot, GCC: time change | One-shot, Clang: time change |
|---|---|---|---|
| ''matches()''; 4 KiB; 128 keys of 12 B each; no matches | preg_match() |
-42.02% | -43.72% |
| ''getMatchedKeywords()''; 4 KiB; 128 keys of 12 B each; one occurrence | preg_match_all() |
-43.01% | -45.20% |
| ''getMatchedKeywords()''; natural-language text (EN), 12,828 B; 128 keys of 4–28 B; 23 occurrences, 12 unique matched keys | strpos() loop |
-68.77% | -66.38% |
| ''replace()''; 4 KiB; 32 keys of 11–21 B; 16 replacements, output length unchanged | preg_replace_callback() |
+111.09% | +118.63% |
| ''replace()''; 16 KiB; the same 32 keys; 16 replacements, output length unchanged | preg_replace_callback() |
-35.67% | -36.06% |
| ''replace()''; 1 MiB; 10,000 keys of 16 B each; no replacements | strtr() |
+362.97% | +400.18% |
| ''replace()''; the same 1 MiB text; 10,000 keys of 8–24 B; no replacements | strtr() |
-63.52% | -63.24% |
For countMatches() and matchAll(), one-shot calls on the same controlled 4 KiB texts with 128 keys were also faster (GCC: -34.34% and -42.75%; Clang: -44.07% and -44.67%). The corresponding inputs and full tables are available in the Matcher report.
The last two rows use the same text with no matches and different dictionaries of 10,000 keys with the same total number of keyword bytes. They show opposite outcomes; keyword lengths and dictionary structure changed together, so the experiment does not isolate a single cause for the difference.
Matcher is worth considering when searching for many literal strings, particularly when the task requires returning unique matched keywords, counting occurrences, or enumerating all occurrences. In the measured configurations, calls on an already prepared Matcher outperformed existing methods even on short texts. For one-shot use, however, construction cost can outweigh the faster matching operation. With 128 keys of 12 B each, one-shot getMatchedKeywords(), countMatches(), and matchAll() were faster on tested texts of 4 KiB and above, but slower on 128 B and 1 KiB texts.
Matcher::matches() scans until the first detected match ends, without performing a separate search for each keyword. By contrast, a str_contains() loop can stop after checking its first keyword if that keyword occurs in the text. It is the PHP loop whose opportunity for this kind of early exit depends strongly on dictionary order. The amount of text scanned affects Matcher time; the number of dictionary entries preceding the matched keyword does not determine how many separate searches are performed. Matcher was often faster on negative inputs and late matches, while early matches could make existing methods much faster.
Replacer is worth trying for a few dozen keys on texts of tens of KiB, or for large dictionaries on long texts. In the tested series with 32 keys of varying lengths, a prepared object was faster already at 4 KiB, but one-shot construction paid off on the tested 16 KiB text. With 16 keys and a 16 KiB text, the one-shot call was slower. These are examples, not universal thresholds.
For a single literal or small dictionaries, consider str_contains(), strpos(), strtr(), and PCRE first. Even a long text does not guarantee a speedup: with eight keys, a strpos() loop could outperform a prepared Matcher. If the prepared method is already slower than an alternative on a given input, repeating it will not reverse that disadvantage.
For replacement, strtr() already performs native multi-pattern replacement. Where keys follow a recognizable format such as rfc, a specialized PCRE expression with dictionary lookup can be much more efficient: on the measured 1 MiB text with 1,000 keys and 100 replacements, it outperformed both modes of Replacer.
When all keys map to the same replacement string, preg_replace() can be used without a PHP callback. It was faster on the tested 69,643 B log text with 24 keys and three replacements. A shared replacement value does not guarantee this outcome, however: on another input (16 KiB, 32 keys, 16 replacements), one-shot Replacer was faster.
In a separate experiment, one Matcher with a dictionary of 128 keys was applied repeatedly to the same 128 B text with no matches. The total time for construction, calls, and destruction was worse than the alternatives at 1, 4, and 16 calls, but better at 64 calls on both compilers. The minimum break-even count was not determined, and no series with different documents was conducted. No comparable repeated-call series was conducted for Replacer. Raw results.
The methods compared produced results with the same semantics, though not necessarily the same PHP types: matchAll() returns MatchResult objects, whereas the alternatives return arrays. The cost of creating and releasing the corresponding results is included in the timings; conversions for correctness checks are not. For full matching, PCRE uses lookahead and groups keywords by length to preserve overlaps. For replacement, the comparisons include strtr() and eligible literal PCRE approaches, including specialized ones for constrained keyword formats.
The main Matcher series uses artificial 12-byte ASCII keywords and text from saved PHP Manual fragments with controlled match positions. After warmup, each measurement repeatedly processes a fixed text–dictionary pair rather than an independent sample of requests. At most 64 occurrences were present in the measured Matcher texts; the performance and memory cost of materializing thousands of MatchResult objects has not been established. Other CPUs, architectures, and full HTTP requests were not measured.
PCRE JIT was enabled, but its actual use for each expression was not confirmed. PHP JIT and OPcache were disabled in these CLI measurements. The warmed-up PCRE cache may persist across requests in a PHP-FPM worker, while application-created objects do not automatically persist across independent requests. Full recipes, measurement quality checks, and raw samples are available in the published study. The measurements do not establish universal thresholds or application-wide speedups.
In the current implementation, the prepared Aho–Corasick automata are built from keywords in forward order for Matcher and reverse order for Replacer. State and transition representations are implementation details, not part of the public contract. Source code.
Let S be the text length, K the number of keywords, U the number of unique matched keywords, H the total number of occurrences, and R the output length. After object construction, the time and additional memory bounds are:
| Operation | Time upper bound | Additional memory, excluding the object and input string |
|---|---|---|
matches() |
O(S), with possible early exit |
O(1) |
countMatches() |
O(S) |
O(1) |
getMatchedKeywords() |
O(S + K + U log U) |
O(K + U) |
matchAll() |
O(S + H log H) |
O(H) |
replace() |
O(S + R) |
O(S + R) in the worst case |
These bounds assume a fixed byte alphabet. Construction cost and object size depend not just on the number of keywords, but also on their total length and shared substrings. With many overlapping occurrences, matchAll() may create a very large array of objects; countMatches() does not materialize them. A streaming interface and a limit on the number of returned results are not proposed.
In the measured Replacer dictionary with 10,000 keywords of 8–24 B each, the object retained about 3.13 MiB beyond the input dictionary, while construction peaked at about 9.16 MiB above the same baseline. These are Zend allocator measurements, not RSS. The peak already includes the object and temporary buffers, so the figures must not be added together. Memory measurement methodology.
The behavior of existing functions does not change. User-defined classes named Str\Matcher, Str\Replacer, or Str\MatchResult will conflict with the new built-in classes. The choice of namespace remains open for discussion.
Neither strtr() nor PCRE is deprecated. Existing applications are not required to migrate to the new API.
The next suitable PHP minor release after acceptance of the RFC, taking the release schedule into account. A specific version will be determined before voting.
No new PHP syntax is introduced. IDEs, language servers, and static analyzers will need descriptions of the classes, result types, and the $count output argument. Signatures and readonly properties are defined in the stub file; the initial value of $count should not be treated as restricted to int.
The proposed placement is ext/standard, under the Str namespace. The current implementation is in ext/strmatch; the final integration approach and its implications for class availability are discussed under Open Issues. Existing extensions remain unchanged.
The API does not specify different behavior for CLI, FPM, or other SAPIs. Class availability will depend on the chosen integration approach.
In PHP-FPM, objects do not automatically persist across independent requests. Reuse means making multiple calls within one request or using a long-running application. This RFC does not propose a persistent automaton cache across requests.
Before voting, the integration and availability of the new API, final names after checking for conflicts, error types, target PHP version, and voting scope must be decided.
The code is currently in ext/strmatch, with build configuration for Unix and Windows; Unix builds provide --enable-strmatch. Using a separate bundled extension named strmatch together with the Str namespace does not comply with the naming policy's name-matching requirement. The policy permits a separate namespace for a new component of ext/standard. Coding Standards and Naming Policy.
The preferred option is to add Str\Matcher, Str\Replacer, and Str\MatchResult as a component of ext/standard. The alternatives open for discussion are:
ext/strmatch and Str.The final names and integration approach will be settled before voting.
The current implementation uses the following error types:
| Situation | Current error type |
|---|---|
| A dictionary element or replacement value has an invalid type | TypeError |
| A dictionary contains an empty search keyword | ValueError |
| The constructor of a prepared object is called again | Error |
| Size or representability limits are exceeded: number of automaton states, number of occurrences, result-array size, or match offset | Error |
Because occurrences may overlap, their total count can exceed the text length. If the result of countMatches() exceeds PHP_INT_MAX, it cannot be returned as a PHP int, so the current implementation throws an Error. Calling the private MatchResult constructor causes PHP's usual access error; out-of-memory conditions are handled by the engine's standard mechanisms.
The final choice of error types remains open. For a new standalone extension, the naming policy provides for an extension-specific exception hierarchy; the standard TypeError and ValueError are allowed for argument validation. Placement in ext/standard also calls for consistency with existing APIs. Throwable policy.
It remains to be decided whether Matcher and Replacer should be accepted in a single vote or independently. With separate votes, the resulting API for each possible outcome must be defined: MatchResult belongs to Matcher. The specific options will be finalized before voting.
Case-insensitive matching, Unicode normalization, replacement callbacks, a streaming interface, a result iterator, automaton serialization, and a persistent cache of prepared objects across requests are outside the scope of this RFC.
The provisional main question, requiring a two-thirds majority, is: Should the Str\Matcher, Str\Replacer, and Str\MatchResult API described in this RFC be accepted?
The final wording, the possibility of separate votes, and the voting dates will be determined after the open issues have been resolved. This document does not yet initiate a vote. RFC process.
The code is available in PR #25122. The revision used for the reported measurements is 7c7550bcdac2091e5f9c256e3f203f82d7db448f. SHA-256 of ext/strmatch/strmatch.c: c4cece7e7a4f5952caae5609b9bc607408427c1fe006e47f59d7fdc0cc0946b3.
The recorded checks include PHPT tests for the API and object lifecycle, comparisons against independent reference implementations, and ASan/UBSan runs. Verification sets are separate: 601 Matcher inputs, 69 inputs in the main Replacer series, and two additional 1 KiB Replacer inputs. All were checked on the corresponding GCC and Clang builds; sanitizer checks were performed separately. Successful results for 16 PHPT tests are recorded for both GCC and Clang. Logs, exact sets, and results.
Correctness checks are not performance measurements. The number of verified inputs does not represent the number of independent documents or measured comparisons.
The listed local GCC, Clang, and sanitizer checks do not replace validation across supported platforms and configurations. Before inclusion in PHP, build and PHPT results for Windows, 32-bit builds, ZTS, and NTS must be recorded separately from the Linux x86-64 benchmark results.
The functionality is not included in any released PHP version. After acceptance and merging, this section will state the PHP version, implementation commit, and a link to the documentation.