4 * This file is part of the Symfony package.
6 * (c) Fabien Potencier <fabien@symfony.com>
8 * For the full copyright and license information, please view the LICENSE
9 * file that was distributed with this source code.
12 namespace Symfony\Component\Routing\Matcher\Dumper;
15 * Prefix tree of routes preserving routes order.
17 * @author Frank de Jonge <info@frankdejonge.nl>
21 class StaticPrefixCollection
29 * @var array[]|StaticPrefixCollection[]
31 private $items = array();
36 private $matchStart = 0;
38 public function __construct($prefix = '')
40 $this->prefix = $prefix;
43 public function getPrefix()
49 * @return mixed[]|StaticPrefixCollection[]
51 public function getItems()
57 * Adds a route to a group.
59 * @param string $prefix
62 public function addRoute($prefix, $route)
64 $prefix = '/' === $prefix ? $prefix : rtrim($prefix, '/');
65 $this->guardAgainstAddingNotAcceptedRoutes($prefix);
67 if ($this->prefix === $prefix) {
68 // When a prefix is exactly the same as the base we move up the match start position.
69 // This is needed because otherwise routes that come afterwards have higher precedence
70 // than a possible regular expression, which goes against the input order sorting.
71 $this->items[] = array($prefix, $route);
72 $this->matchStart = \count($this->items);
77 foreach ($this->items as $i => $item) {
78 if ($i < $this->matchStart) {
82 if ($item instanceof self && $item->accepts($prefix)) {
83 $item->addRoute($prefix, $route);
88 $group = $this->groupWithItem($item, $prefix, $route);
90 if ($group instanceof self) {
91 $this->items[$i] = $group;
97 // No optimised case was found, in this case we simple add the route for possible
98 // grouping when new routes are added.
99 $this->items[] = array($prefix, $route);
103 * Tries to combine a route with another route or group.
105 * @param StaticPrefixCollection|array $item
106 * @param string $prefix
107 * @param mixed $route
109 * @return StaticPrefixCollection|null
111 private function groupWithItem($item, $prefix, $route)
113 $itemPrefix = $item instanceof self ? $item->prefix : $item[0];
114 $commonPrefix = $this->detectCommonPrefix($prefix, $itemPrefix);
116 if (!$commonPrefix) {
120 $child = new self($commonPrefix);
122 if ($item instanceof self) {
123 $child->items = array($item);
125 $child->addRoute($item[0], $item[1]);
128 $child->addRoute($prefix, $route);
134 * Checks whether a prefix can be contained within the group.
136 * @param string $prefix
138 * @return bool Whether a prefix could belong in a given group
140 private function accepts($prefix)
142 return '' === $this->prefix || 0 === strpos($prefix, $this->prefix);
146 * Detects whether there's a common prefix relative to the group prefix and returns it.
148 * @param string $prefix
149 * @param string $anotherPrefix
151 * @return false|string A common prefix, longer than the base/group prefix, or false when none available
153 private function detectCommonPrefix($prefix, $anotherPrefix)
155 $baseLength = \strlen($this->prefix);
156 $commonLength = $baseLength;
157 $end = min(\strlen($prefix), \strlen($anotherPrefix));
159 for ($i = $baseLength; $i <= $end; ++$i) {
160 if (substr($prefix, 0, $i) !== substr($anotherPrefix, 0, $i)) {
167 $commonPrefix = rtrim(substr($prefix, 0, $commonLength), '/');
169 if (\strlen($commonPrefix) > $baseLength) {
170 return $commonPrefix;
177 * Optimizes the tree by inlining items from groups with less than 3 items.
179 public function optimizeGroups()
183 while (isset($this->items[++$index])) {
184 $item = $this->items[$index];
186 if ($item instanceof self) {
187 $item->optimizeGroups();
189 // When a group contains only two items there's no reason to optimize because at minimum
190 // the amount of prefix check is 2. In this case inline the group.
191 if ($item->shouldBeInlined()) {
192 array_splice($this->items, $index, 1, $item->items);
194 // Lower index to pass through the same index again after optimizing.
195 // The first item of the replacements might be a group needing optimization.
202 private function shouldBeInlined()
204 if (\count($this->items) >= 3) {
208 foreach ($this->items as $item) {
209 if ($item instanceof self) {
214 foreach ($this->items as $item) {
215 if (\is_array($item) && $item[0] === $this->prefix) {
224 * Guards against adding incompatible prefixes in a group.
226 * @param string $prefix
228 * @throws \LogicException when a prefix does not belong in a group
230 private function guardAgainstAddingNotAcceptedRoutes($prefix)
232 if (!$this->accepts($prefix)) {
233 $message = sprintf('Could not add route with prefix %s to collection with prefix %s', $prefix, $this->prefix);
235 throw new \LogicException($message);