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
14/**
15 * Prefix tree of routes preserving routes order.
16 *
17 * @author Frank de Jonge <info@frankdejonge.nl>
18 *
19 * @internal
20 */
21class 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}
239