1<?php 2 3/* 4 * This file is part of the Symfony package. 5 * 6 * (c) Fabien Potencier <fabien@symfony.com> 7 * 8 * For the full copyright and license information, please view the LICENSE 9 * file that was distributed with this source code. 10 */ 11 12namespace Symfony\Component\Routing\Matcher\Dumper; 13 14use Symfony\Component\Routing\RouteCollection; 15 16/** 17 * Prefix tree of routes preserving routes order. 18 * 19 * @author Frank de Jonge <info@frankdejonge.nl> 20 * @author Nicolas Grekas <p@tchwork.com> 21 * 22 * @internal 23 */ 24class StaticPrefixCollection 25{ 26 private $prefix; 27 28 /** 29 * @var string[] 30 */ 31 private $staticPrefixes = []; 32 33 /** 34 * @var string[] 35 */ 36 private $prefixes = []; 37 38 /** 39 * @var array[]|self[] 40 */ 41 private $items = []; 42 43 public function __construct(string $prefix = '/') 44 { 45 $this->prefix = $prefix; 46 } 47 48 public function getPrefix(): string 49 { 50 return $this->prefix; 51 } 52 53 /** 54 * @return array[]|self[] 55 */ 56 public function getRoutes(): array 57 { 58 return $this->items; 59 } 60 61 /** 62 * Adds a route to a group. 63 * 64 * @param array|self $route 65 */ 66 public function addRoute(string $prefix, $route) 67 { 68 [$prefix, $staticPrefix] = $this->getCommonPrefix($prefix, $prefix); 69 70 for ($i = \count($this->items) - 1; 0 <= $i; --$i) { 71 $item = $this->items[$i]; 72 73 [$commonPrefix, $commonStaticPrefix] = $this->getCommonPrefix($prefix, $this->prefixes[$i]); 74 75 if ($this->prefix === $commonPrefix) { 76 // the new route and a previous one have no common prefix, let's see if they are exclusive to each others 77 78 if ($this->prefix !== $staticPrefix && $this->prefix !== $this->staticPrefixes[$i]) { 79 // the new route and the previous one have exclusive static prefixes 80 continue; 81 } 82 83 if ($this->prefix === $staticPrefix && $this->prefix === $this->staticPrefixes[$i]) { 84 // the new route and the previous one have no static prefix 85 break; 86 } 87 88 if ($this->prefixes[$i] !== $this->staticPrefixes[$i] && $this->prefix === $this->staticPrefixes[$i]) { 89 // the previous route is non-static and has no static prefix 90 break; 91 } 92 93 if ($prefix !== $staticPrefix && $this->prefix === $staticPrefix) { 94 // the new route is non-static and has no static prefix 95 break; 96 } 97 98 continue; 99 } 100 101 if ($item instanceof self && $this->prefixes[$i] === $commonPrefix) { 102 // the new route is a child of a previous one, let's nest it 103 $item->addRoute($prefix, $route); 104 } else { 105 // the new route and a previous one have a common prefix, let's merge them 106 $child = new self($commonPrefix); 107 [$child->prefixes[0], $child->staticPrefixes[0]] = $child->getCommonPrefix($this->prefixes[$i], $this->prefixes[$i]); 108 [$child->prefixes[1], $child->staticPrefixes[1]] = $child->getCommonPrefix($prefix, $prefix); 109 $child->items = [$this->items[$i], $route]; 110 111 $this->staticPrefixes[$i] = $commonStaticPrefix; 112 $this->prefixes[$i] = $commonPrefix; 113 $this->items[$i] = $child; 114 } 115 116 return; 117 } 118 119 // No optimised case was found, in this case we simple add the route for possible 120 // grouping when new routes are added. 121 $this->staticPrefixes[] = $staticPrefix; 122 $this->prefixes[] = $prefix; 123 $this->items[] = $route; 124 } 125 126 /** 127 * Linearizes back a set of nested routes into a collection. 128 */ 129 public function populateCollection(RouteCollection $routes): RouteCollection 130 { 131 foreach ($this->items as $route) { 132 if ($route instanceof self) { 133 $route->populateCollection($routes); 134 } else { 135 $routes->add(...$route); 136 } 137 } 138 139 return $routes; 140 } 141 142 /** 143 * Gets the full and static common prefixes between two route patterns. 144 * 145 * The static prefix stops at last at the first opening bracket. 146 */ 147 private function getCommonPrefix(string $prefix, string $anotherPrefix): array 148 { 149 $baseLength = \strlen($this->prefix); 150 $end = min(\strlen($prefix), \strlen($anotherPrefix)); 151 $staticLength = null; 152 set_error_handler([__CLASS__, 'handleError']); 153 154 for ($i = $baseLength; $i < $end && $prefix[$i] === $anotherPrefix[$i]; ++$i) { 155 if ('(' === $prefix[$i]) { 156 $staticLength = $staticLength ?? $i; 157 for ($j = 1 + $i, $n = 1; $j < $end && 0 < $n; ++$j) { 158 if ($prefix[$j] !== $anotherPrefix[$j]) { 159 break 2; 160 } 161 if ('(' === $prefix[$j]) { 162 ++$n; 163 } elseif (')' === $prefix[$j]) { 164 --$n; 165 } elseif ('\\' === $prefix[$j] && (++$j === $end || $prefix[$j] !== $anotherPrefix[$j])) { 166 --$j; 167 break; 168 } 169 } 170 if (0 < $n) { 171 break; 172 } 173 if (('?' === ($prefix[$j] ?? '') || '?' === ($anotherPrefix[$j] ?? '')) && ($prefix[$j] ?? '') !== ($anotherPrefix[$j] ?? '')) { 174 break; 175 } 176 $subPattern = substr($prefix, $i, $j - $i); 177 if ($prefix !== $anotherPrefix && !preg_match('/^\(\[[^\]]++\]\+\+\)$/', $subPattern) && !preg_match('{(?<!'.$subPattern.')}', '')) { 178 // sub-patterns of variable length are not considered as common prefixes because their greediness would break in-order matching 179 break; 180 } 181 $i = $j - 1; 182 } elseif ('\\' === $prefix[$i] && (++$i === $end || $prefix[$i] !== $anotherPrefix[$i])) { 183 --$i; 184 break; 185 } 186 } 187 restore_error_handler(); 188 if ($i < $end && 0b10 === (\ord($prefix[$i]) >> 6) && preg_match('//u', $prefix.' '.$anotherPrefix)) { 189 do { 190 // Prevent cutting in the middle of an UTF-8 characters 191 --$i; 192 } while (0b10 === (\ord($prefix[$i]) >> 6)); 193 } 194 195 return [substr($prefix, 0, $i), substr($prefix, 0, $staticLength ?? $i)]; 196 } 197 198 public static function handleError($type, $msg) 199 { 200 return false !== strpos($msg, 'Compilation failed: lookbehind assertion is not fixed length'); 201 } 202} 203