是否存在正则表达式匹配的硬限制


Is there such a thing as a hard limit for regex matching?

我为一个路由组件编写了这段代码,这里是完整的代码,它基本上从许多小的(特定于路由的)正则表达式中构建了一批任意数量的大正则表达式(取决于配置值),以验证给定的请求是否可以或不能被注册路由映射。

一般的过程包括首先装饰每条路由,以便使用像

这样的占位符的路由
/path/to/:variable_name

变成像

一样的正则表达式
/path/to/(?P<R1V1>[^/]+)

在验证时,这些路由被粘合在一个单一的正则表达式中,每批任意大小。

对于"正常"使用,例如500条路由和1-4个占位符,它工作得很好。但是在对其进行基准测试时,我注意到对于大量的占位符以及大量的路由(目前有11个占位符和50000条路由),我的代码无法找到最后注册的路由。

我不明白为什么。据我所知,这个东西应该大致以同样的方式运行,采取(也许?我的O符号已经生锈了)每个数量级的O(n*m)次(n是批的数量,m是批中有多少个正则表达式)。

也许是我测试这个的方式有问题?如果不是,你能指出我现在做的有问题的事情吗?

如果它有用的话,我使用的基准就是这里的这个

<?php
require dirname(__FILE__).'/../vendor/autoload.php';
$router = new 'CFV'Router();
$dispatcher = new 'CFV'Dispatcher();
$dispatcher::$ROUTES_PER_LOT = 20;
// $dispatcher::$THROW_ON_FAIL = true;
$callback = function (){};
$num_args = 11;
$routes_amount = 50000;
$matches_amount = 1;
$args = implode('/', array_map(function($i){ return ':arg' . $i; }, range(1, $num_args)));
$params = implode('/', array_map(function($i){ return '_arg' . $i; }, range(1, $num_args)));
$last_tried = '';
$load_start = microtime(true);
for ($i = 0, $str = 'a'; $i < $routes_amount; $i++, $str++) {
    $router->connect("/$str/$args", $callback);
    $last_tried = "/$str/$params";
}
printf("Took: %fs to load all'n", microtime(true) - $load_start);
$dispatcher->setRouter($router);
$search_start = microtime(true);
$found = $dispatcher->dispatch($last_tried);
printf("Took: %fs searching all'n", microtime(true) - $search_start);

一些限制。从手册:

主题字符串的最大长度是最大的正数一个整型变量所能容纳的。然而,PCRE使用递归来处理子模式和无限重复。这意味着可用的堆栈空间可能会限制主题字符串的大小按一定的模式处理。

还有PCRE的递归极限和回溯极限

如果模式中有超过15个捕获括号,则PCRE有在递归期间获得额外的内存来存储数据,它确实这样做了通过使用pcre_malloc,然后通过pcre_free释放它。如果没有可以获得内存,它保存了前15次捕获的数据只有括号,因为没有办法给出内存不足的错误

裁判:
http://php.net/manual/en/regexp.reference.recursive.php
http://php.net/pcre.configuration ini.pcre.recursion-limit
http://php.net/pcre.configuration ini.pcre.backtrack-limit