PHP: rfc:prepared_literal_string_matching

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== PHP RFC: Prepared Literal String Matching and Replacement ======

  * Version: 0.1
  * Date: 2026-11-02
  * Author: Artem Ukrainskiy, art.ukrainskiy@gmail.com
  * Status: Draft
  * Implementation: https://github.com/php/php-src/pull/25122
  * Discussion thread: TBD
  * Voting thread: TBD

===== Introduction =====

PHP provides several functions for searching and replacing literal substrings, including ''strpos()'', ''str_contains()'', ''str_replace()'', and ''strtr()''. These functions work well for many common tasks, but PHP does not provide a built-in way to prepare a set of literal patterns once and reuse the compiled search structure across multiple input strings.

Applications that check text against large keyword dictionaries, identify multiple terms, or perform repeated substitutions must currently choose between repeated searches, regular expressions, and userland implementations of multi-pattern matching algorithms.

This RFC proposes two classes, ''Str\Matcher'' and ''Str\Replacer'', for prepared literal substring search and replacement.

<PHP>
<?php

$matcher = new Str\Matcher(['error', 'timeout', 'connection refused']);

if ($matcher->matches($message)) {
    // Handle a matching message.
}

$replacer = new Str\Replacer([
    'cat' => 'dog',
    'cats' => 'dogs',
]);

echo $replacer->replace('cats and cat');
// dogs and dog

</PHP>

Both classes prepare an internal matching automaton during construction and can reuse it across multiple subjects.

The implementation uses the Aho-Corasick algorithm. Matching is byte-oriented, binary-safe, and case-sensitive.

===== Proposal =====

The RFC introduces two independent final classes in the ''Str'' namespace, together with a result class.

==== Str\Matcher ====

''Str\Matcher'' prepares a set of literal keywords and provides operations for checking their presence, counting occurrences, and retrieving matching keywords or individual matches.

The proposed API is:

<PHP>
<?php

namespace Str;

final class Matcher
{
    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;
}

</PHP>

The constructor accepts an array of non-empty strings. Duplicate keywords are removed while preserving their original order.

The methods have the following semantics:

  * ''matches()'' returns whether at least one keyword occurs in the subject, stopping at the first match.
  * ''countMatches()'' counts every occurrence, including overlapping occurrences.
  * ''getMatchedKeywords()'' returns each matching keyword once, ordered by its first starting offset, with shorter keywords first when offsets are equal.
  * ''matchAll()'' returns all occurrences as ''MatchResult'' objects, ordered by starting offset, then length.
  * ''getKeywords()'' returns the normalized keyword list.

Offsets and lengths are measured in bytes.

==== Str\Replacer ====

''Str\Replacer'' prepares an associative array mapping literal substrings to their replacements.

<PHP>
<?php

namespace Str;

final class Replacer
{
    public function __construct(array $replacements) {}

    /** @param int $count */
    public function replace(string $subject, &$count = null): string {}

    /** @return array<string|int, string> */
    public function getReplacements(): array {}
}

</PHP>

Replacement follows the literal-array form of ''strtr()'':

  * Process the subject from left to right.
  * At each position, select the longest matching keyword.
  * Replace selected occurrences without overlap.
  * Do not scan replacement text again.
  * Optionally report the number of replacements through ''$count''.

''getReplacements()'' returns the original replacement mapping as a PHP array.

==== Matching semantics and limitations ====

Matching is performed on raw bytes. The implementation does not perform Unicode normalization, case folding, locale-dependent comparisons, or word-boundary detection.

Empty dictionaries are accepted. Empty keywords are rejected.

''Matcher'' requires string keywords, and ''Replacer'' requires string replacement values. Integer replacement-map keys are interpreted as their string representations.

Prepared objects cannot be cloned or serialized, and repeated construction is not permitted.

These restrictions are part of the current implementation and are open to discussion before voting.

==== Performance and memory ====

The primary benefit is amortizing dictionary preparation across multiple subjects.

The prototype uses an alphabet-reduced Aho-Corasick automaton. The replacement implementation uses a reversed automaton to select the longest keyword at each starting position.

Benchmarks compare the proposed API with existing PHP functions and PCRE across different dictionary sizes and workloads, both with and without preparation costs.

The results show substantial benefits for prepared dictionaries in the measured workloads, while existing functions often remain faster for individual operations that include preparation.

The prototype also has memory costs associated with its transition table. A more compact representation may be considered during implementation.

The complete benchmarks, methodology, input corpora, correctness checks, and raw measurements are available at:

https://github.com/ArtUkrainskiy/php-src-bench/tree/main/reports/multi-pattern-search

==== Examples ====

=== Overlapping matches ===

<PHP>
<?php

$matcher = new Str\Matcher(['a', 'aa', 'aaa']);

echo $matcher->countMatches('aaaa');
// 9

foreach ($matcher->matchAll('aaa') as $match) {
    echo "{$match->offset}:{$match->keyword}\n";
}

// 0:a
// 0:aa
// 0:aaa
// 1:a
// 1:aa
// 2:a

</PHP>

=== Longest-match replacement ===

<PHP>
<?php

$replacer = new Str\Replacer([
    'ab' => 'X',
    'abc' => 'Y',
    'bc' => 'Z',
]);

$count = 0;
$result = $replacer->replace('abcab', $count);

var_dump($result); // string(2) "YX"
var_dump($count);  // int(2)

</PHP>

===== Backward Incompatible Changes =====

The proposal introduces three new names:

  * ''Str\Matcher''
  * ''Str\Replacer''
  * ''Str\MatchResult''

Existing functions and language syntax are unchanged.

Applications defining classes with these fully qualified names may encounter naming conflicts when the new extension is enabled.

The extent of existing userland use of these names has not yet been investigated.

===== Proposed PHP Version(s) =====

The next suitable PHP minor release following acceptance of the RFC, subject to the release schedule.

===== RFC Impact =====

==== To the Ecosystem ====

The proposal introduces new internal classes and methods that can be recognized by IDEs, language servers, static analyzers, and documentation tools.

Existing userland APIs and libraries are not modified.

==== To Existing Extensions ====

No changes to existing extensions are proposed.

The reference implementation adds a new ''ext/strmatch'' extension.

==== To SAPIs ====

The API is intended to work across PHP SAPIs, including CLI and PHP-FPM.

Prepared objects have ordinary PHP object lifetimes. They do not automatically persist between independent requests.

Long-running PHP processes may retain and reuse prepared objects across multiple operations.

The proposed feature does not change the execution model, request lifecycle, or threading model of PHP.

===== Open Issues =====

The following questions remain open for discussion:

  * Whether the proposed class names and namespace are appropriate.
  * Whether both classes should be included in the initial proposal.
  * Whether the current public methods and result representation provide the right balance between simplicity and functionality.
  * Whether the prototype's memory representation should be optimized before inclusion.
  * Whether additional operations are necessary for the initial API.

===== Future Scope =====

The following features are outside the scope of this RFC but may be considered separately:

  * Streaming matching across input chunks.
  * Iterator-based retrieval of matches.
  * More compact automaton representations.
  * Optional alternative matching modes.

These features are not required by the proposed API.

===== Voting Choices =====

A primary vote requiring a two-thirds majority is proposed:

**Accept the addition of the Str\Matcher, Str\Replacer, and Str\MatchResult APIs as described in this RFC?**

The voting widget and voting dates will be added when the RFC enters the voting phase.

===== Patches and Tests =====

Reference implementation:

https://github.com/php/php-src/pull/25122

The draft PR includes the C implementation, build configuration for Unix and Windows, and PHPT tests.

Benchmark report:

https://github.com/ArtUkrainskiy/php-src-bench/tree/main/reports/multi-pattern-search

===== Implementation =====

Not yet implemented in a PHP release.

This section will be updated after acceptance and merging.

===== References =====

  * [[https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm|Aho-Corasick string matching algorithm]]
  * [[https://github.com/wikimedia/AhoCorasick|Wikimedia AhoCorasick PHP implementation]]
  * [[https://www.php.net/manual/en/function.strtr.php|PHP strtr() documentation]]
  * [[https://www.php.net/manual/en/function.str-contains.php|PHP str_contains() documentation]]
  * [[https://github.com/php/php-src/pull/25122|Reference implementation]]
  * [[https://github.com/ArtUkrainskiy/php-src-bench/tree/main/reports/multi-pattern-search|Performance investigation]]

===== Rejected Features =====

None at this stage.

===== Changelog =====

  * 2026-11-02: Initial draft.
Page Tools
