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