8000 bug #26208 [Routing] Fix same-prefix aggregation (nicolas-grekas) · symfony/symfony@b1f45b3 · GitHub
[go: up one dir, main page]
Skip to content

Commit b1f45b3

Browse files
fabpotfabpot
committed
bug #26208 [Routing] Fix same-prefix aggregation (nicolas-grekas)
This PR was merged into the 4.1-dev branch. Discussion ---------- [Routing] Fix same-prefix aggregation | Q | A | ------------- | --- | Branch? | master | Bug fix? | yes | New feature? | no | BC breaks? | no | Deprecations? | no | Tests pass? | yes | Fixed tickets | - | License | MIT | Doc PR | - The blog post on http://symfony.com/blog/new-in-symfony-4-1-fastest-php-router made me review the aggregation logic, and discover issues. So now, instead of this: ``` .'|/(en|fr)/admin/post/?(*:82)' .'|/(en|fr)/admin/post/new(*:166)' .'|/(en|fr)/admin/post/(\\d+)(*:253)' .'|/(en|fr)/admin/post/(\\d+)/edit(*:345)' .'|/(en|fr)/admin/post/(\\d+)/delete(*:442)' .'|/(en|fr)/blog/?(*:519)' .'|/(en|fr)/blog/rss\\.xml(*:603)' .'|/(en|fr)/blog/page/([^/]++)(*:694)' .'|/(en|fr)/blog/posts/([^/]++)(*:784)' .'|/(en|fr)/blog/comment/(\d+)/new(*:880)' .'|/(en|fr)/blog/search(*:962)' .'|/(en|fr)/login(*:1038)' .'|/(en|fr)/logout(*:1116)' .'|/(en|fr)?(*:1188)' ``` we generate this: ``` .'|/(en|fr)(?' .'|/admin/post(?' .'|/?(*:34)' .'|/new(*:45)' .'|/(\\d+)(?' .'|(*:61)' .'|/edit(*:73)' .'|/delete(*:87)' .')' .')' .'|/blog(?' .'|/?(*:106)' .'|/rss\\.xml(*:123)' .'|/p(?' .'|age/([^/]++)(*:148)' .'|osts/([^/]++)(*:169)' .')' .'|/comments/(\\d+)/new(*:197)' .'|/search(*:212)' .')' .'|/log(?' .'|in(*:230)' .'|out(*:241)' .')' .')' .'|/(en|fr)?(*:260)' ``` This is not only another perf fix, but a real bug fix, as I found ordering issues. Commits ------- d514f81 [Routing] Fix same-prefix aggregation
2 parents b0facfe + d514f81 commit b1f45b3

File tree

7 files changed

+250
-96
lines changed

7 files changed

+250
-96
lines changed

‎src/Symfony/Component/Routing/Matcher/Dumper/PhpMatcherDumper.php

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -97,10 +97,10 @@ private function generateMatchMethod(bool $supportsRedirections): string
9797
foreach ($this->getRoutes()->all() as $name => $route) {
9898
if ($host = $route->getHost()) {
9999
$matchHost = true;
100-
$host = '/'.str_replace('.', '/', rtrim(explode('}', strrev($host), 2)[0], '.'));
100+
$host = '/'.strtr(strrev($host), '}.{', '(/)');
101101
}
102102

103-
$routes->addRoute($host ?: '/', array($name, $route));
103+
$routes->addRoute($host ?: '/(.*)', array($name, $route));
104104
}
105105
$routes = $matchHost ? $routes->populateCollection(new RouteCollection()) : $this->getRoutes();
106106

@@ -139,7 +139,7 @@ private function compileRoutes(RouteCollection $routes, bool $supportsRedirectio
139139

140140
while (true) {
141141
try {
142-
$this->signalingException = new \RuntimeException('PCRE compilation failed: regular expression is too large');
142+
$this->signalingException = new \RuntimeException('preg_match(): Compilation failed: regular expression is too large');
143143
$code .= $this->compileDynamicRoutes($dynamicRoutes, $supportsRedirections, $matchHost, $chunkLimit);
144144
break;
145145
} catch (\Exception $e) {
@@ -377,7 +377,7 @@ private function compileDynamicRoutes(RouteCollection $collection, bool $support
377377
$state->regex .= $rx;
378378

379379
// if the regex is too large, throw a signaling exception to recompute with smaller chunk size
380-
set_error_handler(function ($type, $message) { throw $this->signalingException; });
380+
set_error_handler(function ($type, $message) { throw 0 === strpos($message, $this->signalingException->getMessage()) ? $this->signalingException : new \ErrorException($message); });
381381
try {
382382
preg_match($state->regex, '');
383383
} finally {

‎src/Symfony/Component/Routing/Matcher/Dumper/StaticPrefixCollection.php

Lines changed: 51 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -17,14 +17,18 @@
1717
* Prefix tree of routes preserving routes order.
1818
*
1919
* @author Frank de Jonge <info@frankdejonge.nl>
20+
* @author Nicolas Grekas <p@tchwork.com>
2021
*
2122
* @internal
2223
*/
2324
class StaticPrefixCollection
2425
{
2526
private $prefix;
26-
private $staticPrefix;
27-
private $matchStart = 0;
27+
28+
/**
29+
* @var string[]
30+
*/
31+
private $staticPrefixes = array();
2832

2933
/**
3034
* @var string[]
@@ -36,10 +40,9 @@ class StaticPrefixCollection
3640
*/
3741
private $items = array();
3842

39-
public function __construct(string $prefix = '/', string $staticPrefix = '/')
43+
public function __construct(string $prefix = '/')
4044
{
4145
$this->prefix = $prefix;
42-
$this->staticPrefix = $staticPrefix;
4346
}
4447

4548
public function getPrefix(): string
@@ -60,41 +63,38 @@ public function getRoutes(): array
6063
*
6164
* @param array|self $route
6265
*/
63-
public function addRoute(string $prefix, $route)
66+
public function addRoute(string $prefix, $route, string $staticPrefix = null)
6467
{
6568
$this->guardAgainstAddingNotAcceptedRoutes($prefix);
66-
list($prefix, $staticPrefix) = $this->detectCommonPrefix($prefix, $prefix) ?: array(rtrim($prefix, '/') ?: '/', '/');
67-
68-
if ($this->staticPrefix === $staticPrefix) {
69-
// When a prefix is exactly the same as the base we move up the match start position.
70-
// This is needed because otherwise routes that come afterwards have higher precedence
71-
// than a possible regular expression, which goes against the input order sorting.
72-
$this->prefixes[] = $prefix;
73-
$this->items[] = $route;
74-
$this->matchStart = count($this->items);
75-
76-
return;
69+
if (null === $staticPrefix) {
70+
list($prefix, $staticPrefix) = $this->getCommonPrefix($prefix, $prefix);
7771
}
7872

79-
for ($i = $this->matchStart; $i < \count($this->items); ++$i) {
73+
for ($i = \count($this->items) - 1; 0 <= $i; --$i) {
8074
$item = $this->items[$i];
8175

8276
if ($item instanceof self && $item->accepts($prefix)) {
83-
$item->addRoute($prefix, $route);
77+
$item->addRoute($prefix, $route, $staticPrefix);
8478

8579
return;
8680
}
8781

88-
if ($group = $this->groupWithItem($i, $prefix, $route)) {
89-
$this->prefixes[$i] = $group->getPrefix();
90-
$this->items[$i] = $group;
91-
82+
if ($this->groupWithItem($i, $prefix, $staticPrefix, $route)) {
9283
return;
9384
}
85+
86+
if ($this->staticPrefixes[$i] !== $this->prefixes[$i] && 0 === strpos($staticPrefix, $this->staticPrefixes[$i])) {
87+
break;
88+
}
89+
90+
if ($staticPrefix !== $prefix && 0 === strpos($this->staticPrefixes[$i], $staticPrefix)) {
91+
break;
92+
}
9493
}
9594

9695
// No optimised case was found, in this case we simple add the route for possible
9796
// grouping when new routes are added.
97+
$this->staticPrefixes[] = $staticPrefix;
9898
$this->prefixes[] = $prefix;
9999
$this->items[] = $route;
100100
}
@@ -118,4 F438 4 +118,44 @@ public function populateCollection(RouteCollection $routes): RouteCollection
118118
/**
119119
* Tries to combine a route with another route or group.
120120
*/
121-
private function groupWithItem(int $i, string $prefix, $route): ?self
121+
private function groupWithItem(int $i, string $prefix, string $staticPrefix, $route): bool
122122
{
123-
if (!$commonPrefix = $this->detectCommonPrefix($prefix, $this->prefixes[$i])) {
124-
return null;
123+
list($commonPrefix, $commonStaticPrefix) = $this->getCommonPrefix($prefix, $this->prefixes[$i]);
124+
125+
if (\strlen($this->prefix) >= \strlen($commonPrefix)) {
126+
return false;
125127
}
126128

127-
$child = new self(...$commonPrefix);
128-
$item = $this->items[$i];
129+
$child = new self($commonPrefix);
129130

130-
if ($item instanceof self) {
131-
$child->prefixes = array($commonPrefix[0]);
132-
$child->items = array($item);
133-
} else {
134-
$child->addRoute($this->prefixes[$i], $item);
135-
}
131+
$child->staticPrefixes = array($this->staticPrefixes[$i], $staticPrefix);
132+
$child->prefixes = array($this->prefixes[$i], $prefix);
133+
$child->items = array($this->items[$i], $route);
136134

137-
$child->addRoute($prefix, $route);
135+
$this->staticPrefixes[$i] = $commonStaticPrefix;
136+
$this->prefixes[$i] = $commonPrefix;
137+
$this->items[$i] = $child;
138138

139-
return $child;
139+
return true;
140140
}
141141

142142
/**
143143
* Checks whether a prefix can be contained within the group.
144144
*/
145145
private function accepts(string $prefix): bool
146146
{
147-
return '' === $this->prefix || 0 === strpos($prefix, $this->prefix);
147+
return 0 === strpos($prefix, $this->prefix) && '?' !== ($prefix[\strlen($this->prefix)] ?? '');
148148
}
149149

150150
/**
151-
* Detects whether there's a common prefix relative to the group prefix and returns it.
151+
* Gets the full and static common prefixes between two route patterns.
152152
*
153-
* @return null|array A common prefix, longer than the base/group prefix, or null when none available
153+
* The static prefix stops at last at the first opening bracket.
154154
*/
155-
private function detectCommonPrefix(string $prefix, string $anotherPrefix): ?array
155+
private function getCommonPrefix(string $prefix, string $anotherPrefix): array
156156
{
157-
$baseLength = strlen($this->prefix);
158-
$end = min(strlen($prefix), strlen($anotherPrefix));
157+
$baseLength = \strlen($this->prefix);
158+
$end = min(\strlen($prefix), \strlen($anotherPrefix));
159159
$staticLength = null;
160160

161161
for ($i = $baseLength; $i < $end && $prefix[$i] === $anotherPrefix[$i]; ++$i) {
@@ -177,21 +177,23 @@ private function detectCommonPrefix(string $prefix, string $anotherPrefix): ?arr
177177
if (0 < $n) {
178178
break;
179179
}
180-
$i = $j;
180+
if (('?' === ($prefix[$j] ?? '') || '?' === ($anotherPrefix[$j] ?? '')) && ($prefix[$j] ?? '') !== ($anotherPrefix[$j] ?? '')) {
181+
break;
182+
}
183+
$i = $j - 1;
181184
} elseif ('\\' === $prefix[$i] && (++$i === $end || $prefix[$i] !== $anotherPrefix[$i])) {
182185
--$i;
183186
break;
184187
}
185188
}
186-
187-
$staticLength = $staticLength ?? $i;
188-
$commonPrefix = rtrim(substr($prefix, 0, $i), '/');
189-
190-
if (strlen($commonPrefix) > $baseLength) {
191-
return array($commonPrefix, rtrim(substr($prefix, 0, $staticLength), '/') ?: '/');
189+
if (1 < $i && '/' === $prefix[$i - 1]) {
190+
--$i;
191+
}
192+
if (null !== $staticLength && 1 < $staticLength && '/' === $prefix[$staticLength - 1]) {
193+
--$staticLength;
192194
}
193195

194-
return null;
196+
return array(substr($prefix, 0, $i), substr($prefix, 0, $staticLength ?? $i));
195197
}
196198

197199
/**

‎src/Symfony/Component/Routing/Tests/Fixtures/dumper/url_matcher1.php

Lines changed: 23 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -98,23 +98,25 @@ public function match($rawPathinfo)
9898
.')'
9999
.')'
100100
.'|/multi/hello(?:/([^/]++))?(*:238)'
101-
.'|/([^/]++)/b/([^/]++)(*:266)'
102-
.'|/([^/]++)/b/([^/]++)(*:294)'
103-
.'|/aba/([^/]++)(*:315)'
101+
.'|/([^/]++)/b/([^/]++)(?'
102+
.'|(*:269)'
103+
.'|(*:277)'
104+
.')'
105+
.'|/aba/([^/]++)(*:299)'
104106
.')|(?i:([^\\.]++)\\.example\\.com)(?'
105107
.'|/route1(?'
106-
.'|3/([^/]++)(*:375)'
107-
.'|4/([^/]++)(*:393)'
108+
.'|3/([^/]++)(*:359)'
109+
.'|4/([^/]++)(*:377)'
108110
.')'
109111
.')|(?i:c\\.example\\.com)(?'
110-
.'|/route15/([^/]++)(*:443)'
112+
.'|/route15/([^/]++)(*:427)'
111113
.')|[^/]*+(?'
112-
.'|/route16/([^/]++)(*:478)'
114+
.'|/route16/([^/]++)(*:462)'
113115
.'|/a(?'
114-
.'|/a\\.\\.\\.(*:499)'
116+
.'|/a\\.\\.\\.(*:483)'
115117
.'|/b(?'
116-
.'|/([^/]++)(*:521)'
117-
.'|/c/([^/]++)(*:540)'
118+
.'|/([^/]++)(*:505)'
119+
.'|/c/([^/]++)(*:524)'
118120
.')'
119121
.')'
120122
.')'
@@ -172,7 +174,7 @@ public function match($rawPathinfo)
172174
return $this->mergeDefaults(array_replace($matches, array('_route' => 'foo2')), array());
173175

174176
break;
175-
case 266:
177+
case 269:
176178
$matches = array('_locale' => $matches[1] ?? null, 'foo' => $matches[2] ?? null);
177179

178180
// foo3
@@ -189,15 +191,15 @@ public function match($rawPathinfo)
189191
170 => array(array('_route' => 'overridden'), array('var'), null, null),
190192
202 => array(array('_route' => 'bar2'), array('bar1'), null, null),
191193
238 => array(array('_route' => 'helloWorld', 'who' => 'World!'), array('who'), null, null),
192-
294 => array(array('_route' => 'bar3'), array('_locale', 'bar'), null, null),
193-
315 => array(array('_route' => 'foo4'), array('foo'), null, null),
194-
375 => array(array('_route' => 'route13'), array('var1', 'name'), null, null),
195-
393 => array(array('_route' => 'route14', 'var1' => 'val'), array('var1', 'name'), null, null),
196-
443 => array(array('_route' => 'route15'), array('name'), null, null),
197-
478 => array(array('_route' => 'route16', 'var1' => 'val'), array('name'), null, null),
198-
499 => array(array('_route' => 'a'), array(), null, null),
199-
521 => array(array('_route' => 'b'), array('var'), null, null),
200-
540 => array(array('_route' => 'c'), array('var'), null, null),
194+
277 => array(array('_route' => 'bar3'), array('_locale', 'bar'), null, null),
195+
299 => array(array('_route' => 'foo4'), array('foo'), null, null),
196+
359 => array(array('_route' => 'route13'), array('var1', 'name'), null, null),
197+
377 => array(array('_route' => 'route14', 'var1' => 'val'), array('var1', 'name'), null, null),
198+
427 => array(array('_route' => 'route15'), array('name'), null, null),
199+
462 => array(array('_route' => 'route16', 'var1' => 'val'), array('name'), null, null),
200+
483 => array(array('_route' => 'a'), array(), null, null),
201+
505 => array(array('_route' => 'b'), array('var'), null, null),
202+
524 => array(array('_route' => 'c'), array('var'), null, null),
201203
);
202204

203205
list($ret, $vars, $requiredMethods, $requiredSchemes) = $routes[$m];
@@ -216,7 +218,7 @@ public function match($rawPathinfo)
216218
return $ret;
217219
}
218220

219-
if (540 === $m) {
221+
if (524 === $m) {
220222
break;
221223
}
222224
$regex = substr_replace($regex, 'F', $m - $offset, 1 + strlen($m));

0 commit comments

Comments
 (0)
0