annotate vendor/symfony/routing/Matcher/Dumper/StaticPrefixCollection.php @ 19:fa3358dc1485 tip

Add ndrum files
author Chris Cannam
date Wed, 28 Aug 2019 13:14:47 +0100
parents 129ea1e6d783
children
rev   line source
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 }