Chris@14
|
1 <?php
|
Chris@14
|
2
|
Chris@14
|
3 /*
|
Chris@14
|
4 * This file is part of the Symfony package.
|
Chris@14
|
5 *
|
Chris@14
|
6 * (c) Fabien Potencier <fabien@symfony.com>
|
Chris@14
|
7 *
|
Chris@14
|
8 * For the full copyright and license information, please view the LICENSE
|
Chris@14
|
9 * file that was distributed with this source code.
|
Chris@14
|
10 */
|
Chris@14
|
11
|
Chris@14
|
12 namespace Symfony\Component\Routing\Matcher\Dumper;
|
Chris@14
|
13
|
Chris@14
|
14 /**
|
Chris@14
|
15 * Prefix tree of routes preserving routes order.
|
Chris@14
|
16 *
|
Chris@14
|
17 * @author Frank de Jonge <info@frankdejonge.nl>
|
Chris@14
|
18 *
|
Chris@14
|
19 * @internal
|
Chris@14
|
20 */
|
Chris@14
|
21 class StaticPrefixCollection
|
Chris@14
|
22 {
|
Chris@14
|
23 /**
|
Chris@14
|
24 * @var string
|
Chris@14
|
25 */
|
Chris@14
|
26 private $prefix;
|
Chris@14
|
27
|
Chris@14
|
28 /**
|
Chris@14
|
29 * @var array[]|StaticPrefixCollection[]
|
Chris@14
|
30 */
|
Chris@17
|
31 private $items = [];
|
Chris@14
|
32
|
Chris@14
|
33 /**
|
Chris@14
|
34 * @var int
|
Chris@14
|
35 */
|
Chris@14
|
36 private $matchStart = 0;
|
Chris@14
|
37
|
Chris@14
|
38 public function __construct($prefix = '')
|
Chris@14
|
39 {
|
Chris@14
|
40 $this->prefix = $prefix;
|
Chris@14
|
41 }
|
Chris@14
|
42
|
Chris@14
|
43 public function getPrefix()
|
Chris@14
|
44 {
|
Chris@14
|
45 return $this->prefix;
|
Chris@14
|
46 }
|
Chris@14
|
47
|
Chris@14
|
48 /**
|
Chris@14
|
49 * @return mixed[]|StaticPrefixCollection[]
|
Chris@14
|
50 */
|
Chris@14
|
51 public function getItems()
|
Chris@14
|
52 {
|
Chris@14
|
53 return $this->items;
|
Chris@14
|
54 }
|
Chris@14
|
55
|
Chris@14
|
56 /**
|
Chris@14
|
57 * Adds a route to a group.
|
Chris@14
|
58 *
|
Chris@14
|
59 * @param string $prefix
|
Chris@14
|
60 * @param mixed $route
|
Chris@14
|
61 */
|
Chris@14
|
62 public function addRoute($prefix, $route)
|
Chris@14
|
63 {
|
Chris@14
|
64 $prefix = '/' === $prefix ? $prefix : rtrim($prefix, '/');
|
Chris@14
|
65 $this->guardAgainstAddingNotAcceptedRoutes($prefix);
|
Chris@14
|
66
|
Chris@14
|
67 if ($this->prefix === $prefix) {
|
Chris@14
|
68 // When a prefix is exactly the same as the base we move up the match start position.
|
Chris@14
|
69 // This is needed because otherwise routes that come afterwards have higher precedence
|
Chris@14
|
70 // than a possible regular expression, which goes against the input order sorting.
|
Chris@17
|
71 $this->items[] = [$prefix, $route];
|
Chris@17
|
72 $this->matchStart = \count($this->items);
|
Chris@14
|
73
|
Chris@14
|
74 return;
|
Chris@14
|
75 }
|
Chris@14
|
76
|
Chris@14
|
77 foreach ($this->items as $i => $item) {
|
Chris@14
|
78 if ($i < $this->matchStart) {
|
Chris@14
|
79 continue;
|
Chris@14
|
80 }
|
Chris@14
|
81
|
Chris@14
|
82 if ($item instanceof self && $item->accepts($prefix)) {
|
Chris@14
|
83 $item->addRoute($prefix, $route);
|
Chris@14
|
84
|
Chris@14
|
85 return;
|
Chris@14
|
86 }
|
Chris@14
|
87
|
Chris@14
|
88 $group = $this->groupWithItem($item, $prefix, $route);
|
Chris@14
|
89
|
Chris@14
|
90 if ($group instanceof self) {
|
Chris@14
|
91 $this->items[$i] = $group;
|
Chris@14
|
92
|
Chris@14
|
93 return;
|
Chris@14
|
94 }
|
Chris@14
|
95 }
|
Chris@14
|
96
|
Chris@14
|
97 // No optimised case was found, in this case we simple add the route for possible
|
Chris@14
|
98 // grouping when new routes are added.
|
Chris@17
|
99 $this->items[] = [$prefix, $route];
|
Chris@14
|
100 }
|
Chris@14
|
101
|
Chris@14
|
102 /**
|
Chris@14
|
103 * Tries to combine a route with another route or group.
|
Chris@14
|
104 *
|
Chris@14
|
105 * @param StaticPrefixCollection|array $item
|
Chris@14
|
106 * @param string $prefix
|
Chris@14
|
107 * @param mixed $route
|
Chris@14
|
108 *
|
Chris@17
|
109 * @return StaticPrefixCollection|null
|
Chris@14
|
110 */
|
Chris@14
|
111 private function groupWithItem($item, $prefix, $route)
|
Chris@14
|
112 {
|
Chris@14
|
113 $itemPrefix = $item instanceof self ? $item->prefix : $item[0];
|
Chris@14
|
114 $commonPrefix = $this->detectCommonPrefix($prefix, $itemPrefix);
|
Chris@14
|
115
|
Chris@14
|
116 if (!$commonPrefix) {
|
Chris@14
|
117 return;
|
Chris@14
|
118 }
|
Chris@14
|
119
|
Chris@14
|
120 $child = new self($commonPrefix);
|
Chris@14
|
121
|
Chris@14
|
122 if ($item instanceof self) {
|
Chris@17
|
123 $child->items = [$item];
|
Chris@14
|
124 } else {
|
Chris@14
|
125 $child->addRoute($item[0], $item[1]);
|
Chris@14
|
126 }
|
Chris@14
|
127
|
Chris@14
|
128 $child->addRoute($prefix, $route);
|
Chris@14
|
129
|
Chris@14
|
130 return $child;
|
Chris@14
|
131 }
|
Chris@14
|
132
|
Chris@14
|
133 /**
|
Chris@14
|
134 * Checks whether a prefix can be contained within the group.
|
Chris@14
|
135 *
|
Chris@14
|
136 * @param string $prefix
|
Chris@14
|
137 *
|
Chris@14
|
138 * @return bool Whether a prefix could belong in a given group
|
Chris@14
|
139 */
|
Chris@14
|
140 private function accepts($prefix)
|
Chris@14
|
141 {
|
Chris@14
|
142 return '' === $this->prefix || 0 === strpos($prefix, $this->prefix);
|
Chris@14
|
143 }
|
Chris@14
|
144
|
Chris@14
|
145 /**
|
Chris@14
|
146 * Detects whether there's a common prefix relative to the group prefix and returns it.
|
Chris@14
|
147 *
|
Chris@14
|
148 * @param string $prefix
|
Chris@14
|
149 * @param string $anotherPrefix
|
Chris@14
|
150 *
|
Chris@14
|
151 * @return false|string A common prefix, longer than the base/group prefix, or false when none available
|
Chris@14
|
152 */
|
Chris@14
|
153 private function detectCommonPrefix($prefix, $anotherPrefix)
|
Chris@14
|
154 {
|
Chris@17
|
155 $baseLength = \strlen($this->prefix);
|
Chris@14
|
156 $commonLength = $baseLength;
|
Chris@17
|
157 $end = min(\strlen($prefix), \strlen($anotherPrefix));
|
Chris@14
|
158
|
Chris@14
|
159 for ($i = $baseLength; $i <= $end; ++$i) {
|
Chris@14
|
160 if (substr($prefix, 0, $i) !== substr($anotherPrefix, 0, $i)) {
|
Chris@14
|
161 break;
|
Chris@14
|
162 }
|
Chris@14
|
163
|
Chris@14
|
164 $commonLength = $i;
|
Chris@14
|
165 }
|
Chris@14
|
166
|
Chris@14
|
167 $commonPrefix = rtrim(substr($prefix, 0, $commonLength), '/');
|
Chris@14
|
168
|
Chris@17
|
169 if (\strlen($commonPrefix) > $baseLength) {
|
Chris@14
|
170 return $commonPrefix;
|
Chris@14
|
171 }
|
Chris@14
|
172
|
Chris@14
|
173 return false;
|
Chris@14
|
174 }
|
Chris@14
|
175
|
Chris@14
|
176 /**
|
Chris@14
|
177 * Optimizes the tree by inlining items from groups with less than 3 items.
|
Chris@14
|
178 */
|
Chris@14
|
179 public function optimizeGroups()
|
Chris@14
|
180 {
|
Chris@14
|
181 $index = -1;
|
Chris@14
|
182
|
Chris@14
|
183 while (isset($this->items[++$index])) {
|
Chris@14
|
184 $item = $this->items[$index];
|
Chris@14
|
185
|
Chris@14
|
186 if ($item instanceof self) {
|
Chris@14
|
187 $item->optimizeGroups();
|
Chris@14
|
188
|
Chris@14
|
189 // When a group contains only two items there's no reason to optimize because at minimum
|
Chris@14
|
190 // the amount of prefix check is 2. In this case inline the group.
|
Chris@14
|
191 if ($item->shouldBeInlined()) {
|
Chris@14
|
192 array_splice($this->items, $index, 1, $item->items);
|
Chris@14
|
193
|
Chris@14
|
194 // Lower index to pass through the same index again after optimizing.
|
Chris@14
|
195 // The first item of the replacements might be a group needing optimization.
|
Chris@14
|
196 --$index;
|
Chris@14
|
197 }
|
Chris@14
|
198 }
|
Chris@14
|
199 }
|
Chris@14
|
200 }
|
Chris@14
|
201
|
Chris@14
|
202 private function shouldBeInlined()
|
Chris@14
|
203 {
|
Chris@17
|
204 if (\count($this->items) >= 3) {
|
Chris@14
|
205 return false;
|
Chris@14
|
206 }
|
Chris@14
|
207
|
Chris@14
|
208 foreach ($this->items as $item) {
|
Chris@14
|
209 if ($item instanceof self) {
|
Chris@14
|
210 return true;
|
Chris@14
|
211 }
|
Chris@14
|
212 }
|
Chris@14
|
213
|
Chris@14
|
214 foreach ($this->items as $item) {
|
Chris@17
|
215 if (\is_array($item) && $item[0] === $this->prefix) {
|
Chris@14
|
216 return false;
|
Chris@14
|
217 }
|
Chris@14
|
218 }
|
Chris@14
|
219
|
Chris@14
|
220 return true;
|
Chris@14
|
221 }
|
Chris@14
|
222
|
Chris@14
|
223 /**
|
Chris@14
|
224 * Guards against adding incompatible prefixes in a group.
|
Chris@14
|
225 *
|
Chris@14
|
226 * @param string $prefix
|
Chris@14
|
227 *
|
Chris@14
|
228 * @throws \LogicException when a prefix does not belong in a group
|
Chris@14
|
229 */
|
Chris@14
|
230 private function guardAgainstAddingNotAcceptedRoutes($prefix)
|
Chris@14
|
231 {
|
Chris@14
|
232 if (!$this->accepts($prefix)) {
|
Chris@14
|
233 $message = sprintf('Could not add route with prefix %s to collection with prefix %s', $prefix, $this->prefix);
|
Chris@14
|
234
|
Chris@14
|
235 throw new \LogicException($message);
|
Chris@14
|
236 }
|
Chris@14
|
237 }
|
Chris@14
|
238 }
|