RegexGenerator::getPrefix() - Code Metrics - Inspection of "Performance Update" - divineniiquaye/flight-routing - Measure and Improve Code Quality continuously with Scrutinizer

Test Failed

Pull Request — master (#16)

by Divine Niiquaye

created 2021-09-17 01:49 UTC

RegexGenerator::getPrefix() A

↳ Parent: RegexGenerator

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	1
eloc	1
nc	1
nop	0
dl	0
loc	3
rs	10
c	0
b	0
f	0

<?php

declare(strict_types=1);

/*
 * This file is part of Flight Routing.
 *
 * PHP version 7.1 and above required
 *
 * @author    Divine Niiquaye Ibok <[email protected]>
 * @copyright 2019 Biurad Group (https://biurad.com/)
 * @license   https://opensource.org/licenses/BSD-3-Clause License
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace Flight\Routing\Generator;

use Flight\Routing\Routes\FastRoute;
use Flight\Routing\Interfaces\RouteCompilerInterface;

/**
 * A helper Prefix tree class to help help in the compilation of routes in
 * preserving routes order as a full regex excluding modifies.
 *
 * This class is retrieved from symfony's routing component to add
 * high performance into Flight Routing and avoid requiring the whole component.
 *
 * @author Frank de Jonge <[email protected]>
 * @author Nicolas Grekas <[email protected]>
 * @author Divine Niiquaye Ibok <[email protected]>
 *
 * @internal
 */
class RegexGenerator
{
    /** @var string */
    private $prefix;

    /** @var string[] */
    private $staticPrefixes = [];

    /** @var string[] */
    private $prefixes = [];

    /** @var array[]|self[] */
    private $items = [];

    public function __construct(string $prefix = '/')
    {
        $this->prefix = $prefix;
    }

    public function getPrefix(): string
    {
        return $this->prefix;
    }

    /**
     * @return array[]|self[]
     */
    public function getRoutes(): array
    {
        return $this->items;
    }

    /**
     * This method uses default routes compiler.
     *
     * @param array<int,FastRoute> $routes
     *
     * @return array<int,mixed>
     */
    public static function beforeCaching(RouteCompilerInterface $compiler, array $routes): array
    {
        $tree = new static();
        $indexedRoutes = [];

        for ($i = 0; $i < \count($routes); ++$i) {
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
            [$pathRegex, $hostsRegex, $variables] = $compiler->compile($route = $routes[$i]);
            $pathRegex = \preg_replace('/\?(?|P<\w+>|<\w+>|\'\w+\')/', '', $pathRegex);

            $tree->addRoute($pathRegex, [$pathRegex, $i, [$route, $hostsRegex, $variables]]);
        }

        $compiledRegex = '~^(?' . $tree->compile(0, $indexedRoutes) . ')$~u';
        \ksort($indexedRoutes);

        return [$compiledRegex, $indexedRoutes, $compiler];
    }

    /**
     * Compiles a regexp tree of sub-patterns that matches nested same-prefix routes.
     *
     * The route item should contain:
     * - pathRegex
     * - an id used for (*:MARK)
     * - an array of additional/optional values if maybe required.
     */
    public function compile(int $prefixLen, array &$variables = []): string
    {
        $code = '';

        foreach ($this->items as $route) {
            if ($route instanceof self) {
                $prefix = \substr($route->prefix, $prefixLen);
                $code .= '|' . \ltrim($prefix, '?') . '(?' . $route->compile($prefixLen + \strlen($prefix), $variables) . ')';

                continue;
            }

            $code .= '|' . \substr($route[0], $prefixLen) . '(*:' . $route[1] . ')';
            $variables[$route[1]] = $route[2];
        }

        return $code;
    }

    /**
     * Adds a route to a group.
     *
     * @param array|self $route
     */
    public function addRoute(string $prefix, $route): void
    {
        [$prefix, $staticPrefix] = $this->getCommonPrefix($prefix, $prefix);

        for ($i = \count($this->items) - 1; 0 <= $i; --$i) {
            $item = $this->items[$i];

            [$commonPrefix, $commonStaticPrefix] = $this->getCommonPrefix($prefix, $this->prefixes[$i]);

            if ($this->prefix === $commonPrefix) {
                // the new route and a previous one have no common prefix, let's see if they are exclusive to each others

                if ($this->prefix !== $staticPrefix && $this->prefix !== $this->staticPrefixes[$i]) {
                    // the new route and the previous one have exclusive static prefixes
                    continue;
                }

                if ($this->prefix === $staticPrefix && $this->prefix === $this->staticPrefixes[$i]) {
                    // the new route and the previous one have no static prefix
                    break;
                }

                if ($this->prefixes[$i] !== $this->staticPrefixes[$i] && $this->prefix === $this->staticPrefixes[$i]) {
                    // the previous route is non-static and has no static prefix
                    break;
                }

                if ($prefix !== $staticPrefix && $this->prefix === $staticPrefix) {
                    // the new route is non-static and has no static prefix
                    break;
                }

                continue;
            }

            if ($item instanceof self && $this->prefixes[$i] === $commonPrefix) {
                // the new route is a child of a previous one, let's nest it
                $item->addRoute($prefix, $route);
            } else {
                // the new route and a previous one have a common prefix, let's merge them
                $child = new self($commonPrefix);
                [$child->prefixes[0], $child->staticPrefixes[0]] = $child->getCommonPrefix($this->prefixes[$i], $this->prefixes[$i]);
                [$child->prefixes[1], $child->staticPrefixes[1]] = $child->getCommonPrefix($prefix, $prefix);
                $child->items = [$this->items[$i], $route];

                $this->staticPrefixes[$i] = $commonStaticPrefix;
                $this->prefixes[$i] = $commonPrefix;
                $this->items[$i] = $child;
            }

            return;
        }

        // No optimised case was found, in this case we simple add the route for possible
        // grouping when new routes are added.
        $this->staticPrefixes[] = $staticPrefix;
        $this->prefixes[] = $prefix;
        $this->items[] = $route;
    }

    public static function handleError(int $type, string $msg): bool
    {
        return false !== \strpos($msg, 'Compilation failed: lookbehind assertion is not fixed length');
    }

    /**
     * Gets the full and static common prefixes between two route patterns.
     *
     * The static prefix stops at last at the first opening bracket.
     */
    private function getCommonPrefix(string $prefix, string $anotherPrefix): array
    {
        $baseLength = \strlen($this->prefix);
        $end = \min(\strlen($prefix), \strlen($anotherPrefix));
        $staticLength = null;
        \set_error_handler([__CLASS__, 'handleError']);

        for ($i = $baseLength; $i < $end && $prefix[$i] === $anotherPrefix[$i]; ++$i) {
            if ('(' === $prefix[$i]) {
                $staticLength = $staticLength ?? $i;

                for ($j = 1 + $i, $n = 1; $j < $end && 0 < $n; ++$j) {
                    if ($prefix[$j] !== $anotherPrefix[$j]) {
                        break 2;
                    }

                    if ('(' === $prefix[$j]) {
                        ++$n;
                    } elseif (')' === $prefix[$j]) {
                        --$n;
                    } elseif ('\\' === $prefix[$j] && (++$j === $end || $prefix[$j] !== $anotherPrefix[$j])) {
                        --$j;

                        break;
                    }
                }

                if (0 < $n) {
                    break;
                }

                if (('?' === ($prefix[$j] ?? '') || '?' === ($anotherPrefix[$j] ?? '')) && ($prefix[$j] ?? '') !== ($anotherPrefix[$j] ?? '')) {
                    break;
                }
                $subPattern = \substr($prefix, $i, $j - $i);

                if ($prefix !== $anotherPrefix && !\preg_match('/^\(\[[^\]]++\]\+\+\)$/', $subPattern) && !\preg_match('{(?<!' . $subPattern . ')}', '')) {
                    // sub-patterns of variable length are not considered as common prefixes because their greediness would break in-order matching
                    break;
                }
                $i = $j - 1;
            } elseif ('\\' === $prefix[$i] && (++$i === $end || $prefix[$i] !== $anotherPrefix[$i])) {
                --$i;

                break;
            }
        }

        \restore_error_handler();

        if ($i < $end && 0b10 === (\ord($prefix[$i]) >> 6) && \preg_match('//u', $prefix . ' ' . $anotherPrefix)) {
            do {
                // Prevent cutting in the middle of an UTF-8 characters
                --$i;
            } while (0b10 === (\ord($prefix[$i]) >> 6));
        }

        return [\substr($prefix, 0, $i), \substr($prefix, 0, $staticLength ?? $i)];
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			/*
6			* This file is part of Flight Routing.
7			*
8			* PHP version 7.1 and above required
9			*
10			* @author Divine Niiquaye Ibok <[email protected]>
11			* @copyright 2019 Biurad Group (https://biurad.com/)
12			* @license https://opensource.org/licenses/BSD-3-Clause License
13			*
14			* For the full copyright and license information, please view the LICENSE
15			* file that was distributed with this source code.
16			*/
17
18			namespace Flight\Routing\Generator;
19
20			use Flight\Routing\Routes\FastRoute;
21			use Flight\Routing\Interfaces\RouteCompilerInterface;
22
23			/**
24			* A helper Prefix tree class to help help in the compilation of routes in
25			* preserving routes order as a full regex excluding modifies.
26			*
27			* This class is retrieved from symfony's routing component to add
28			* high performance into Flight Routing and avoid requiring the whole component.
29			*
30			* @author Frank de Jonge <[email protected]>
31			* @author Nicolas Grekas <[email protected]>
32			* @author Divine Niiquaye Ibok <[email protected]>
33			*
34			* @internal
35			*/
36			class RegexGenerator
37			{
38			/** @var string */
39			private $prefix;
40
41			/** @var string[] */
42			private $staticPrefixes = [];
43
44			/** @var string[] */
45			private $prefixes = [];
46
47			/** @var array[]\|self[] */
48			private $items = [];
49
50			public function __construct(string $prefix = '/')
51			{
52			$this->prefix = $prefix;
53			}
54
55			public function getPrefix(): string
56			{
57			return $this->prefix;
58			}
59
60			/**
61			* @return array[]\|self[]
62			*/
63			public function getRoutes(): array
64			{
65			return $this->items;
66			}
67
68			/**
69			* This method uses default routes compiler.
70			*
71			* @param array<int,FastRoute> $routes
72			*
73			* @return array<int,mixed>
74			*/
75			public static function beforeCaching(RouteCompilerInterface $compiler, array $routes): array
76			{
77			$tree = new static();
78			$indexedRoutes = [];
79
80			for ($i = 0; $i < \count($routes); ++$i) {
			0 ignored issues – show Performance Best Practice introduced 2021-09-13 02:38 UTC by Report Bug Copy Issue Report It seems like you are calling the size function `count()` as part of the test condition. You might want to compute the size beforehand, and not on each iteration. If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration } // Better for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once } Loading history...
81			[$pathRegex, $hostsRegex, $variables] = $compiler->compile($route = $routes[$i]);
82			$pathRegex = \preg_replace('/\?(?\|P<\w+>\|<\w+>\|\'\w+\')/', '', $pathRegex);
83
84			$tree->addRoute($pathRegex, [$pathRegex, $i, [$route, $hostsRegex, $variables]]);
85			}
86
87			$compiledRegex = '~^(?' . $tree->compile(0, $indexedRoutes) . ')$~u';
88			\ksort($indexedRoutes);
89
90			return [$compiledRegex, $indexedRoutes, $compiler];
91			}
92
93			/**
94			* Compiles a regexp tree of sub-patterns that matches nested same-prefix routes.
95			*
96			* The route item should contain:
97			* - pathRegex
98			* - an id used for (*:MARK)
99			* - an array of additional/optional values if maybe required.
100			*/
101			public function compile(int $prefixLen, array &$variables = []): string
102			{
103			$code = '';
104
105			foreach ($this->items as $route) {
106			if ($route instanceof self) {
107			$prefix = \substr($route->prefix, $prefixLen);
108			$code .= '\|' . \ltrim($prefix, '?') . '(?' . $route->compile($prefixLen + \strlen($prefix), $variables) . ')';
109
110			continue;
111			}
112
113			$code .= '\|' . \substr($route[0], $prefixLen) . '(*:' . $route[1] . ')';
114			$variables[$route[1]] = $route[2];
115			}
116
117			return $code;
118			}
119
120			/**
121			* Adds a route to a group.
122			*
123			* @param array\|self $route
124			*/
125			public function addRoute(string $prefix, $route): void
126			{
127			[$prefix, $staticPrefix] = $this->getCommonPrefix($prefix, $prefix);
128
129			for ($i = \count($this->items) - 1; 0 <= $i; --$i) {
130			$item = $this->items[$i];
131
132			[$commonPrefix, $commonStaticPrefix] = $this->getCommonPrefix($prefix, $this->prefixes[$i]);
133
134			if ($this->prefix === $commonPrefix) {
135			// the new route and a previous one have no common prefix, let's see if they are exclusive to each others
136
137			if ($this->prefix !== $staticPrefix && $this->prefix !== $this->staticPrefixes[$i]) {
138			// the new route and the previous one have exclusive static prefixes
139			continue;
140			}
141
142			if ($this->prefix === $staticPrefix && $this->prefix === $this->staticPrefixes[$i]) {
143			// the new route and the previous one have no static prefix
144			break;
145			}
146
147			if ($this->prefixes[$i] !== $this->staticPrefixes[$i] && $this->prefix === $this->staticPrefixes[$i]) {
148			// the previous route is non-static and has no static prefix
149			break;
150			}
151
152			if ($prefix !== $staticPrefix && $this->prefix === $staticPrefix) {
153			// the new route is non-static and has no static prefix
154			break;
155			}
156
157			continue;
158			}
159
160			if ($item instanceof self && $this->prefixes[$i] === $commonPrefix) {
161			// the new route is a child of a previous one, let's nest it
162			$item->addRoute($prefix, $route);
163			} else {
164			// the new route and a previous one have a common prefix, let's merge them
165			$child = new self($commonPrefix);
166			[$child->prefixes[0], $child->staticPrefixes[0]] = $child->getCommonPrefix($this->prefixes[$i], $this->prefixes[$i]);
167			[$child->prefixes[1], $child->staticPrefixes[1]] = $child->getCommonPrefix($prefix, $prefix);
168			$child->items = [$this->items[$i], $route];
169
170			$this->staticPrefixes[$i] = $commonStaticPrefix;
171			$this->prefixes[$i] = $commonPrefix;
172			$this->items[$i] = $child;
173			}
174
175			return;
176			}
177
178			// No optimised case was found, in this case we simple add the route for possible
179			// grouping when new routes are added.
180			$this->staticPrefixes[] = $staticPrefix;
181			$this->prefixes[] = $prefix;
182			$this->items[] = $route;
183			}
184
185			public static function handleError(int $type, string $msg): bool
186			{
187			return false !== \strpos($msg, 'Compilation failed: lookbehind assertion is not fixed length');
188			}
189
190			/**
191			* Gets the full and static common prefixes between two route patterns.
192			*
193			* The static prefix stops at last at the first opening bracket.
194			*/
195			private function getCommonPrefix(string $prefix, string $anotherPrefix): array
196			{
197			$baseLength = \strlen($this->prefix);
198			$end = \min(\strlen($prefix), \strlen($anotherPrefix));
199			$staticLength = null;
200			\set_error_handler([__CLASS__, 'handleError']);
201
202			for ($i = $baseLength; $i < $end && $prefix[$i] === $anotherPrefix[$i]; ++$i) {
203			if ('(' === $prefix[$i]) {
204			$staticLength = $staticLength ?? $i;
205
206			for ($j = 1 + $i, $n = 1; $j < $end && 0 < $n; ++$j) {
207			if ($prefix[$j] !== $anotherPrefix[$j]) {
208			break 2;
209			}
210
211			if ('(' === $prefix[$j]) {
212			++$n;
213			} elseif (')' === $prefix[$j]) {
214			--$n;
215			} elseif ('\\' === $prefix[$j] && (++$j === $end \|\| $prefix[$j] !== $anotherPrefix[$j])) {
216			--$j;
217
218			break;
219			}
220			}
221
222			if (0 < $n) {
223			break;
224			}
225
226			if (('?' === ($prefix[$j] ?? '') \|\| '?' === ($anotherPrefix[$j] ?? '')) && ($prefix[$j] ?? '') !== ($anotherPrefix[$j] ?? '')) {
227			break;
228			}
229			$subPattern = \substr($prefix, $i, $j - $i);
230
231			if ($prefix !== $anotherPrefix && !\preg_match('/^\(\[[^\]]++\]\+\+\)$/', $subPattern) && !\preg_match('{(?<!' . $subPattern . ')}', '')) {
232			// sub-patterns of variable length are not considered as common prefixes because their greediness would break in-order matching
233			break;
234			}
235			$i = $j - 1;
236			} elseif ('\\' === $prefix[$i] && (++$i === $end \|\| $prefix[$i] !== $anotherPrefix[$i])) {
237			--$i;
238
239			break;
240			}
241			}
242
243			\restore_error_handler();
244
245			if ($i < $end && 0b10 === (\ord($prefix[$i]) >> 6) && \preg_match('//u', $prefix . ' ' . $anotherPrefix)) {
246			do {
247			// Prevent cutting in the middle of an UTF-8 characters
248			--$i;
249			} while (0b10 === (\ord($prefix[$i]) >> 6));
250			}
251
252			return [\substr($prefix, 0, $i), \substr($prefix, 0, $staticLength ?? $i)];
253			}
254			}
255

divineniiquaye / flight-routing

Pull Request — master (#16)

RegexGenerator::getPrefix() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like