StaticPrefixCollection.php 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239
  1. <?php
  2. /*
  3. * This file is part of the Symfony package.
  4. *
  5. * (c) Fabien Potencier <fabien@symfony.com>
  6. *
  7. * For the full copyright and license information, please view the LICENSE
  8. * file that was distributed with this source code.
  9. */
  10. namespace Symfony\Component\Routing\Matcher\Dumper;
  11. /**
  12. * Prefix tree of routes preserving routes order.
  13. *
  14. * @author Frank de Jonge <info@frankdejonge.nl>
  15. *
  16. * @internal
  17. */
  18. class StaticPrefixCollection
  19. {
  20. /**
  21. * @var string
  22. */
  23. private $prefix;
  24. /**
  25. * @var array[]|StaticPrefixCollection[]
  26. */
  27. private $items = array();
  28. /**
  29. * @var int
  30. */
  31. private $matchStart = 0;
  32. public function __construct($prefix = '')
  33. {
  34. $this->prefix = $prefix;
  35. }
  36. public function getPrefix()
  37. {
  38. return $this->prefix;
  39. }
  40. /**
  41. * @return mixed[]|StaticPrefixCollection[]
  42. */
  43. public function getItems()
  44. {
  45. return $this->items;
  46. }
  47. /**
  48. * Adds a route to a group.
  49. *
  50. * @param string $prefix
  51. * @param mixed $route
  52. */
  53. public function addRoute($prefix, $route)
  54. {
  55. $prefix = '/' === $prefix ? $prefix : rtrim($prefix, '/');
  56. $this->guardAgainstAddingNotAcceptedRoutes($prefix);
  57. if ($this->prefix === $prefix) {
  58. // When a prefix is exactly the same as the base we move up the match start position.
  59. // This is needed because otherwise routes that come afterwards have higher precedence
  60. // than a possible regular expression, which goes against the input order sorting.
  61. $this->items[] = array($prefix, $route);
  62. $this->matchStart = count($this->items);
  63. return;
  64. }
  65. foreach ($this->items as $i => $item) {
  66. if ($i < $this->matchStart) {
  67. continue;
  68. }
  69. if ($item instanceof self && $item->accepts($prefix)) {
  70. $item->addRoute($prefix, $route);
  71. return;
  72. }
  73. $group = $this->groupWithItem($item, $prefix, $route);
  74. if ($group instanceof self) {
  75. $this->items[$i] = $group;
  76. return;
  77. }
  78. }
  79. // No optimised case was found, in this case we simple add the route for possible
  80. // grouping when new routes are added.
  81. $this->items[] = array($prefix, $route);
  82. }
  83. /**
  84. * Tries to combine a route with another route or group.
  85. *
  86. * @param StaticPrefixCollection|array $item
  87. * @param string $prefix
  88. * @param mixed $route
  89. *
  90. * @return null|StaticPrefixCollection
  91. */
  92. private function groupWithItem($item, $prefix, $route)
  93. {
  94. $itemPrefix = $item instanceof self ? $item->prefix : $item[0];
  95. $commonPrefix = $this->detectCommonPrefix($prefix, $itemPrefix);
  96. if (!$commonPrefix) {
  97. return;
  98. }
  99. $child = new self($commonPrefix);
  100. if ($item instanceof self) {
  101. $child->items = array($item);
  102. } else {
  103. $child->addRoute($item[0], $item[1]);
  104. }
  105. $child->addRoute($prefix, $route);
  106. return $child;
  107. }
  108. /**
  109. * Checks whether a prefix can be contained within the group.
  110. *
  111. * @param string $prefix
  112. *
  113. * @return bool Whether a prefix could belong in a given group
  114. */
  115. private function accepts($prefix)
  116. {
  117. return '' === $this->prefix || strpos($prefix, $this->prefix) === 0;
  118. }
  119. /**
  120. * Detects whether there's a common prefix relative to the group prefix and returns it.
  121. *
  122. * @param string $prefix
  123. * @param string $anotherPrefix
  124. *
  125. * @return false|string A common prefix, longer than the base/group prefix, or false when none available
  126. */
  127. private function detectCommonPrefix($prefix, $anotherPrefix)
  128. {
  129. $baseLength = strlen($this->prefix);
  130. $commonLength = $baseLength;
  131. $end = min(strlen($prefix), strlen($anotherPrefix));
  132. for ($i = $baseLength; $i <= $end; ++$i) {
  133. if (substr($prefix, 0, $i) !== substr($anotherPrefix, 0, $i)) {
  134. break;
  135. }
  136. $commonLength = $i;
  137. }
  138. $commonPrefix = rtrim(substr($prefix, 0, $commonLength), '/');
  139. if (strlen($commonPrefix) > $baseLength) {
  140. return $commonPrefix;
  141. }
  142. return false;
  143. }
  144. /**
  145. * Optimizes the tree by inlining items from groups with less than 3 items.
  146. */
  147. public function optimizeGroups()
  148. {
  149. $index = -1;
  150. while (isset($this->items[++$index])) {
  151. $item = $this->items[$index];
  152. if ($item instanceof self) {
  153. $item->optimizeGroups();
  154. // When a group contains only two items there's no reason to optimize because at minimum
  155. // the amount of prefix check is 2. In this case inline the group.
  156. if ($item->shouldBeInlined()) {
  157. array_splice($this->items, $index, 1, $item->items);
  158. // Lower index to pass through the same index again after optimizing.
  159. // The first item of the replacements might be a group needing optimization.
  160. --$index;
  161. }
  162. }
  163. }
  164. }
  165. private function shouldBeInlined()
  166. {
  167. if (count($this->items) >= 3) {
  168. return false;
  169. }
  170. foreach ($this->items as $item) {
  171. if ($item instanceof self) {
  172. return true;
  173. }
  174. }
  175. foreach ($this->items as $item) {
  176. if (is_array($item) && $item[0] === $this->prefix) {
  177. return false;
  178. }
  179. }
  180. return true;
  181. }
  182. /**
  183. * Guards against adding incompatible prefixes in a group.
  184. *
  185. * @param string $prefix
  186. *
  187. * @throws \LogicException When a prefix does not belong in a group.
  188. */
  189. private function guardAgainstAddingNotAcceptedRoutes($prefix)
  190. {
  191. if (!$this->accepts($prefix)) {
  192. $message = sprintf('Could not add route with prefix %s to collection with prefix %s', $prefix, $this->prefix);
  193. throw new \LogicException($message);
  194. }
  195. }
  196. }