123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239 |
- <?php
- /*
- * This file is part of the Symfony package.
- *
- * (c) Fabien Potencier <fabien@symfony.com>
- *
- * For the full copyright and license information, please view the LICENSE
- * file that was distributed with this source code.
- */
- namespace Symfony\Component\Routing\Matcher\Dumper;
- /**
- * Prefix tree of routes preserving routes order.
- *
- * @author Frank de Jonge <info@frankdejonge.nl>
- *
- * @internal
- */
- class StaticPrefixCollection
- {
- /**
- * @var string
- */
- private $prefix;
- /**
- * @var array[]|StaticPrefixCollection[]
- */
- private $items = array();
- /**
- * @var int
- */
- private $matchStart = 0;
- public function __construct($prefix = '')
- {
- $this->prefix = $prefix;
- }
- public function getPrefix()
- {
- return $this->prefix;
- }
- /**
- * @return mixed[]|StaticPrefixCollection[]
- */
- public function getItems()
- {
- return $this->items;
- }
- /**
- * Adds a route to a group.
- *
- * @param string $prefix
- * @param mixed $route
- */
- public function addRoute($prefix, $route)
- {
- $prefix = '/' === $prefix ? $prefix : rtrim($prefix, '/');
- $this->guardAgainstAddingNotAcceptedRoutes($prefix);
- if ($this->prefix === $prefix) {
- // When a prefix is exactly the same as the base we move up the match start position.
- // This is needed because otherwise routes that come afterwards have higher precedence
- // than a possible regular expression, which goes against the input order sorting.
- $this->items[] = array($prefix, $route);
- $this->matchStart = count($this->items);
- return;
- }
- foreach ($this->items as $i => $item) {
- if ($i < $this->matchStart) {
- continue;
- }
- if ($item instanceof self && $item->accepts($prefix)) {
- $item->addRoute($prefix, $route);
- return;
- }
- $group = $this->groupWithItem($item, $prefix, $route);
- if ($group instanceof self) {
- $this->items[$i] = $group;
- return;
- }
- }
- // No optimised case was found, in this case we simple add the route for possible
- // grouping when new routes are added.
- $this->items[] = array($prefix, $route);
- }
- /**
- * Tries to combine a route with another route or group.
- *
- * @param StaticPrefixCollection|array $item
- * @param string $prefix
- * @param mixed $route
- *
- * @return null|StaticPrefixCollection
- */
- private function groupWithItem($item, $prefix, $route)
- {
- $itemPrefix = $item instanceof self ? $item->prefix : $item[0];
- $commonPrefix = $this->detectCommonPrefix($prefix, $itemPrefix);
- if (!$commonPrefix) {
- return;
- }
- $child = new self($commonPrefix);
- if ($item instanceof self) {
- $child->items = array($item);
- } else {
- $child->addRoute($item[0], $item[1]);
- }
- $child->addRoute($prefix, $route);
- return $child;
- }
- /**
- * Checks whether a prefix can be contained within the group.
- *
- * @param string $prefix
- *
- * @return bool Whether a prefix could belong in a given group
- */
- private function accepts($prefix)
- {
- return '' === $this->prefix || strpos($prefix, $this->prefix) === 0;
- }
- /**
- * Detects whether there's a common prefix relative to the group prefix and returns it.
- *
- * @param string $prefix
- * @param string $anotherPrefix
- *
- * @return false|string A common prefix, longer than the base/group prefix, or false when none available
- */
- private function detectCommonPrefix($prefix, $anotherPrefix)
- {
- $baseLength = strlen($this->prefix);
- $commonLength = $baseLength;
- $end = min(strlen($prefix), strlen($anotherPrefix));
- for ($i = $baseLength; $i <= $end; ++$i) {
- if (substr($prefix, 0, $i) !== substr($anotherPrefix, 0, $i)) {
- break;
- }
- $commonLength = $i;
- }
- $commonPrefix = rtrim(substr($prefix, 0, $commonLength), '/');
- if (strlen($commonPrefix) > $baseLength) {
- return $commonPrefix;
- }
- return false;
- }
- /**
- * Optimizes the tree by inlining items from groups with less than 3 items.
- */
- public function optimizeGroups()
- {
- $index = -1;
- while (isset($this->items[++$index])) {
- $item = $this->items[$index];
- if ($item instanceof self) {
- $item->optimizeGroups();
- // When a group contains only two items there's no reason to optimize because at minimum
- // the amount of prefix check is 2. In this case inline the group.
- if ($item->shouldBeInlined()) {
- array_splice($this->items, $index, 1, $item->items);
- // Lower index to pass through the same index again after optimizing.
- // The first item of the replacements might be a group needing optimization.
- --$index;
- }
- }
- }
- }
- private function shouldBeInlined()
- {
- if (count($this->items) >= 3) {
- return false;
- }
- foreach ($this->items as $item) {
- if ($item instanceof self) {
- return true;
- }
- }
- foreach ($this->items as $item) {
- if (is_array($item) && $item[0] === $this->prefix) {
- return false;
- }
- }
- return true;
- }
- /**
- * Guards against adding incompatible prefixes in a group.
- *
- * @param string $prefix
- *
- * @throws \LogicException When a prefix does not belong in a group.
- */
- private function guardAgainstAddingNotAcceptedRoutes($prefix)
- {
- if (!$this->accepts($prefix)) {
- $message = sprintf('Could not add route with prefix %s to collection with prefix %s', $prefix, $this->prefix);
- throw new \LogicException($message);
- }
- }
- }
|