Skip to content

[Routing] Handle very large set of dynamic routes #26169

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Feb 14, 2018
Merged

[Routing] Handle very large set of dynamic routes #26169

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
76 changes: 51 additions & 25 deletions src/Symfony/Component/Routing/Matcher/Dumper/PhpMatcherDumper.php
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -27,6 +27,7 @@
class PhpMatcherDumper extends MatcherDumper
{
private $expressionLanguage;
private $signalingException;

/**
* @var ExpressionFunctionProviderInterface[]
Expand Down Expand Up @@ -87,12 +88,8 @@ public function addExpressionLanguageProvider(ExpressionFunctionProviderInterfac

/**
* Generates the code for the match method implementing UrlMatcherInterface.
*
* @param bool $supportsRedirections Whether redirections are supported by the base class
*
* @return string Match method as PHP code
*/
private function generateMatchMethod($supportsRedirections)
private function generateMatchMethod(bool $supportsRedirections): string
{
// Group hosts by same-suffix, re-order when possible
$matchHost = false;
Expand Down Expand Up @@ -132,18 +129,27 @@ public function match(\$rawPathinfo)

/**
* Generates PHP code to match a RouteCollection with all its routes.
*
* @param RouteCollection $routes A RouteCollection instance
* @param bool $supportsRedirections Whether redirections are supported by the base class
*
* @return string PHP code
*/
private function compileRoutes(RouteCollection $routes, $supportsRedirections, $matchHost)
private function compileRoutes(RouteCollection $routes, bool $supportsRedirections, bool $matchHost): string
{
list($staticRoutes, $dynamicRoutes) = $this->groupStaticRoutes($routes, $supportsRedirections);

$code = $this->compileStaticRoutes($staticRoutes, $supportsRedirections, $matchHost);
$code .= $this->compileDynamicRoutes($dynamicRoutes, $supportsRedirections, $matchHost);
$chunkLimit = count($dynamicRoutes);

while (true) {
try {
$this->signalingException = new \RuntimeException('PCRE compilation failed: regular expression is too large');
$code .= $this->compileDynamicRoutes($dynamicRoutes, $supportsRedirections, $matchHost, $chunkLimit);
break;
} catch (\Exception $e) {
if (1 < $chunkLimit && $this->signalingException === $e) {
$chunkLimit = 1 + ($chunkLimit >> 1);
continue;
}
throw $e;
}
}

if ('' === $code) {
$code .= " if ('/' === \$pathinfo) {\n";
Expand Down Expand Up @@ -275,13 +281,14 @@ private function compileStaticRoutes(array $staticRoutes, bool $supportsRedirect
* matching-but-failing subpattern is blacklisted by replacing its name by "(*F)", which forces a failure-to-match.
* To ease this backlisting operation, the name of subpatterns is also the string offset where the replacement should occur.
*/
private function compileDynamicRoutes(RouteCollection $collection, bool $supportsRedirections, bool $matchHost): string
private function compileDynamicRoutes(RouteCollection $collection, bool $supportsRedirections, bool $matchHost, int $chunkLimit): string
{
if (!$collection->all()) {
return '';
}
$code = '';
$state = (object) array(
'regex' => '',
'switch' => '',
'default' => '',
'mark' => 0,
Expand All @@ -301,11 +308,13 @@ private function compileDynamicRoutes(RouteCollection $collection, bool $support
return '';
};

$chunkSize = 0;
$prev = null;
$perModifiers = array();
foreach ($collection->all() as $name => $route) {
preg_match('#[a-zA-Z]*$#', $route->compile()->getRegex(), $rx);
if ($prev !== $rx[0] && $route->compile()->getPathVariables()) {
if ($chunkLimit < ++$chunkSize || $prev !== $rx[0] && $route->compile()->getPathVariables()) {
$chunkSize = 1;
$routes = new RouteCollection();
$perModifiers[] = array($rx[0], $routes);
$prev = $rx[0];
Expand All @@ -326,8 +335,10 @@ private function compileDynamicRoutes(RouteCollection $collection, bool $support
$routes->add($name, $route);
}
$prev = false;
$code .= "\n {$state->mark} => '{^(?'";
$state->mark += 4;
$rx = '{^(?';
$code .= "\n {$state->mark} => ".self::export($rx);
$state->mark += strlen($rx);
$state->regex = $rx;

foreach ($perHost as list($hostRegex, $routes)) {
if ($matchHost) {
Expand All @@ -340,8 +351,9 @@ private function compileDynamicRoutes(RouteCollection $collection, bool $support
$hostRegex = '[^/]*+';
$state->hostVars = array();
}
$state->mark += 3 + $prev + strlen($hostRegex);
$code .= "\n .".self::export(($prev ? ')' : '')."|{$hostRegex}(?");
$state->mark += strlen($rx = ($prev ? ')' : '')."|{$hostRegex}(?");
$code .= "\n .".self::export($rx);
$state->regex .= $rx;
$prev = true;
}

Expand All @@ -358,8 +370,19 @@ private function compileDynamicRoutes(RouteCollection $collection, bool $support
}
if ($matchHost) {
$code .= "\n .')'";
$state->regex .= ')';
}
$rx = ")$}{$modifiers}";
$code .= "\n .'{$rx}',";
$state->regex .= $rx;

// if the regex is too large, throw a signaling exception to recompute with smaller chunk size
Copy link
Contributor

@ro0NL ro0NL Feb 13, 2018 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

curious... why not have (reasonably large) fixed limit instead? is it variable in case of PCRE? It could avoid any recomputing needed no?

edit: wait this is compile info.. right? It gives the best chunk limit possible

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Because I have absolutely no idea what would that mean in practice, and the current logic saves me from answering this question :)

Copy link
Contributor

@ro0NL ro0NL Feb 13, 2018 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The large fixture is a result of this choice i guess.. in theory that could break tests in different envs.. 🤔 should it be mocked?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not sure we should care about such concerns.

set_error_handler(function ($type, $message) { throw $this->signalingException; });
try {
preg_match($state->regex, '');
} finally {
restore_error_handler();
}
$code .= "\n .')$}{$modifiers}',";
}

if ($state->default) {
Expand Down Expand Up @@ -403,7 +426,7 @@ private function compileDynamicRoutes(RouteCollection $collection, bool $support
* @param \stdClass $state A simple state object that keeps track of the progress of the compilation,
* and gathers the generated switch's "case" and "default" statements
*/
private function compileStaticPrefixCollection(StaticPrefixCollection $tree, \stdClass $state, int $prefixLen = 0)
private function compileStaticPrefixCollection(StaticPrefixCollection $tree, \stdClass $state, int $prefixLen = 0): string
{
$code = '';
$prevRegex = null;
Expand All @@ -413,10 +436,12 @@ private function compileStaticPrefixCollection(StaticPrefixCollection $tree, \st
if ($route instanceof StaticPrefixCollection) {
$prevRegex = null;
$prefix = substr($route->getPrefix(), $prefixLen);
$state->mark += 3 + strlen($prefix);
$code .= "\n .".self::export("|{$prefix}(?");
$state->mark += strlen($rx = "|{$prefix}(?");
$code .= "\n .".self::export($rx);
$state->regex .= $rx;
$code .= $this->indent($this->compileStaticPrefixCollection($route, $state, $prefixLen + strlen($prefix)));
$code .= "\n .')'";
$state->regex .= ')';
$state->markTail += 1;
continue;
}
Expand All @@ -434,8 +459,9 @@ private function compileStaticPrefixCollection(StaticPrefixCollection $tree, \st
$hasTrailingSlash = $hasTrailingSlash && (!$methods || isset($methods['GET']));
$state->mark += 3 + $state->markTail + $hasTrailingSlash + strlen($regex) - $prefixLen;
$state->markTail = 2 + strlen($state->mark);
$code .= "\n .";
$code .= self::export(sprintf('|%s(*:%s)', substr($regex, $prefixLen).($hasTrailingSlash ? '?' : ''), $state->mark));
$rx = sprintf('|%s(*:%s)', substr($regex, $prefixLen).($hasTrailingSlash ? '?' : ''), $state->mark);
$code .= "\n .".self::export($rx);
$state->regex .= $rx;
$vars = array_merge($state->hostVars, $vars);

if (!$route->getCondition() && (!is_array($next = $routes[1 + $i] ?? null) || $regex !== $next[1])) {
Expand Down Expand Up @@ -472,7 +498,7 @@ private function compileStaticPrefixCollection(StaticPrefixCollection $tree, \st
/**
* A simple helper to compiles the switch's "default" for both static and dynamic routes.
*/
private function compileSwitchDefault(bool $hasVars, string $routesKey, bool $matchHost, bool $supportsRedirections, bool $checkTrailingSlash)
private function compileSwitchDefault(bool $hasVars, string $routesKey, bool $matchHost, bool $supportsRedirections, bool $checkTrailingSlash): string
{
if ($hasVars) {
$code = <<<EOF
Expand Down
Loading