<?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 = [];
/**
* @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[] = [$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[] = [$prefix, $route];
}
/**
* Tries to combine a route with another route or group.
*
* @param StaticPrefixCollection|array $item
* @param string $prefix
* @param mixed $route
*
* @return StaticPrefixCollection|null
*/
private function groupWithItem($item, $prefix, $route)
{
$itemPrefix = $item instanceof self ? $item->prefix : $item[0];
$commonPrefix = $this->detectCommonPrefix($prefix, $itemPrefix);
if (!$commonPrefix) {
return null;
}
$child = new self($commonPrefix);
if ($item instanceof self) {
$child->items = [$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 || 0 === strpos($prefix, $this->prefix);
}
/**
* 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);
}
}
}