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