[Summary view] [Print] [Text view]

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