Glob::getStaticPrefix() - Code Metrics - Inspection of "Path pruning" - phpDocumentor/FlyFinder - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — master (#15)

unknown

created 2019-12-21 23:40 UTC

Glob::getStaticPrefix() B

↳ Parent: Glob

Complexity

Conditions	9
Paths	9

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	29
rs	8.0555
c	0
b	0
f	0
cc	9
nc	9
nop	1

<?php

declare(strict_types=1);

/**
 * This file is part of phpDocumentor.
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 *
 * Many thanks to webmozart by providing the original code in webmozart/glob
 *
 * @link https://github.com/webmozart/glob/blob/master/src/Glob.php
 * @link      http://phpdoc.org
 */

namespace Flyfinder\Specification;

use Flyfinder\Path;
use InvalidArgumentException;
use function preg_match;
use function sprintf;
use function strlen;
use function strpos;

/**
 * Glob specification class
 *
 * @psalm-immutable
 */
final class Glob extends CompositeSpecification
{
    /** @var string */
    private $regex;

    /**
     * The "static prefix" is the part of the glob up to the first wildcard "*".
     * If the glob does not contain wildcards, the full glob is returned.
     *
     * @var string
     */
    private $staticPrefix;

    /**
     * The "bounded prefix" is the part of the glob up to the first recursive wildcard "**".
     * It is the longest prefix for which the number of directory segments in the partial match
     * is known. If the glob does not contain the recursive wildcard "**", the full glob is returned.
     * @var string
     */
    private $boundedPrefix;

    /**
     * The "total prefix" is the part of the glob before the trailing catch-all wildcard sequence if the glob
     * ends with one, otherwise null. It is needed for implementing the A-quantifier pruning hint.
     * @var string
     */
    private $totalPrefix;

    public function __construct(string $glob)
    {
        $this->regex            = self::toRegEx($glob);
        $this->staticPrefix     = self::getStaticPrefix($glob);
        $this->boundedPrefix    = self::getBoundedPrefix($glob);
        $this->totalPrefix      = self::getTotalPrefix($glob);
    }

    /**
     * @inheritDoc
     */
    public function isSatisfiedBy(array $value) : bool
    {
        //Flysystem paths are not absolute, so make it that way.
        $path = '/' . $value['path'];
        if (strpos($path, $this->staticPrefix) !== 0) {
            return false;
        }

        if (preg_match($this->regex, $path)) {
            return true;
        }

        return false;
    }

    /**
     * Returns the static prefix of a glob.
     *
     * The "static prefix" is the part of the glob up to the first wildcard "*".
     * If the glob does not contain wildcards, the full glob is returned.
     *
     * @param string $glob The canonical glob. The glob should contain forward
     *                      slashes as directory separators only. It must not
     *                      contain any "." or ".." segments.
     *
     * @return string The static prefix of the glob.
     *
     * @psalm-pure
     */
    private static function getStaticPrefix(string $glob) : string
    {
        self::assertValidGlob($glob);
        $prefix = '';
        $length = strlen($glob);
        for ($i = 0; $i < $length; ++$i) {
            $c = $glob[$i];
            switch ($c) {
                case '/':
                    $prefix .= '/';
                    if (self::isRecursiveWildcard($glob, $i)) {
                        break 2;
                    }
                    break;
                case '*':
                case '?':
                case '{':
                case '[':
                    break 2;
                case '\\':
                    self::scanBackslashSequence($prefix, $glob, $i);
                    break;
                default:
                    $prefix .= $c;
                    break;
            }
        }
        return $prefix;
    }

    private static function getBoundedPrefix(string $glob) : string
    {
        self::assertValidGlob($glob);
        $prefix = '';
        $length = strlen($glob);
        for($i=0; $i < $length; ++$i) {
            $c = $glob[$i];
            switch ($c) {
                case '/':
                    $prefix .= '/';
                    if(self::isRecursiveWildcard($glob, $i)) {
                        break 2;
                    }
                    break;
                case '\\':
                    self::scanBackslashSequence($prefix, $glob, $i);
                    break;
                default:
                    $prefix .= $c;
                    break;
            }
        }
        return $prefix;
    }

    private static function getTotalPrefix(string $glob) : ?string
    {
        self::assertValidGlob($glob);
        $matches=[];
        return preg_match('~(?<!\\\\)/\\*\\*(?:/\\*\\*?)+$~', $glob, $matches)
            ? substr($glob,0,strlen($glob)-strlen($matches[0]))
            : null;
    }

    private static function scanBackslashSequence(string &$prefix, string $glob, int &$i) : void
    {
            switch ($c = $glob[$i + 1] ?? '') {
                case '*':
                case '?':
                case '{':
                case '}':
                case '[':
                case ']':
                case '-':
                case '^':
                case '$':
                case '~':
                case '\\':
                    $prefix .= $c;
                    ++$i;
                    break;
                default:
                    $prefix .= '\\';
            }
    }

    /**
     * @param string $glob
     */
    private static function assertValidGlob(string $glob): void
    {
        if (strpos($glob, '/') !== 0 && strpos($glob, '://') === false) {
            throw new InvalidArgumentException(sprintf(
                'The glob "%s" is not absolute and not a URI.',
                $glob
            ));
        }
    }

    /**
     * Checks if the current position the glob is start of a Recursive directory wildcard
     *
     * @psalm-pure
     */
    private static function isRecursiveWildcard(string $glob, int $i) : bool
    {
        return isset($glob[$i + 3]) && $glob[$i + 1] . $glob[$i + 2] . $glob[$i + 3] === '**/';
    }

    /**
     * Converts a glob to a regular expression.
     *
     * @param string $glob The canonical glob. The glob should contain forward
     *                      slashes as directory separators only. It must not
     *                      contain any "." or ".." segments.
     *
     * @return string The regular expression for matching the glob.
     *
     * @psalm-pure
     */
    private static function toRegEx(string $glob) : string
    {
        $delimiter   = '~';
        $inSquare    = false;
        $curlyLevels = 0;
        $regex       = '';
        $length      = strlen($glob);
        for ($i = 0; $i < $length; ++$i) {
            $c = $glob[$i];
            switch ($c) {
                case '.':
                case '(':
                case ')':
                case '|':
                case '+':
                case '^':
                case '$':
                case $delimiter:
                    $regex .= '\\' . $c;
                    break;
                case '/':
                    if (self::isRecursiveWildcard($glob, $i)) {
                        $regex .= '/([^/]+/)*';
                        $i     += 3;
                    } else {
                        $regex .= '/';
                    }
                    break;
                case '*':
                    $regex .= '[^/]*';
                    break;
                case '?':
                    $regex .= '.';
                    break;
                case '{':
                    $regex .= '(';
                    ++$curlyLevels;
                    break;
                case '}':
                    if ($curlyLevels > 0) {
                        $regex .= ')';
                        --$curlyLevels;
                    } else {
                        $regex .= '}';
                    }
                    break;
                case ',':
                    $regex .= $curlyLevels > 0 ? '|' : ',';
                    break;
                case '[':
                    $regex   .= '[';
                    $inSquare = true;
                    if (isset($glob[$i + 1]) && $glob[$i + 1] === '^') {
                        $regex .= '^';
                        ++$i;
                    }
                    break;
                case ']':
                    $regex   .= $inSquare ? ']' : '\\]';
                    $inSquare = false;
                    break;
                case '-':
                    $regex .= $inSquare ? '-' : '\\-';
                    break;
                case '\\':
                    if (isset($glob[$i + 1])) {
                        switch ($glob[$i + 1]) {
                            case '*':
                            case '?':
                            case '{':
                            case '}':
                            case '[':
                            case ']':
                            case '-':
                            case '^':
                            case '$':
                            case '~':
                            case '\\':
                                $regex .= '\\' . $glob[$i + 1];
                                ++$i;
                                break;
                            default:
                                $regex .= '\\\\';
                        }
                    }
                    break;
                default:
                    $regex .= $c;
                    break;
            }
        }
        if ($inSquare) {
            throw new InvalidArgumentException(sprintf(
                'Invalid glob: missing ] in %s',
                $glob
            ));
        }
        if ($curlyLevels > 0) {
            throw new InvalidArgumentException(sprintf(
                'Invalid glob: missing } in %s',
                $glob
            ));
        }
        return $delimiter . '^' . $regex . '$' . $delimiter;
    }

    /** @inheritDoc */
    public function canBeSatisfiedBySomethingBelow(array $value): bool
    {
        $valueSegments = explode('/','/'.$value['path']);
        $valueSegmentsCount = count($valueSegments);
        $boundedPrefixGlobSegments = explode('/',rtrim($this->boundedPrefix,'/'));
        $boundedPrefixGlobSegmentsCount = count($boundedPrefixGlobSegments);
        $howManySegmentsToConsider = min($valueSegmentsCount,$boundedPrefixGlobSegmentsCount);
        $boundedPrefixGlob = implode('/',array_slice($boundedPrefixGlobSegments, 0, $howManySegmentsToConsider));
        $valuePathPrefix = implode('/',array_slice($valueSegments, 1, max($howManySegmentsToConsider-1,0)));
        $prefixValue = $value;
        $prefixValue['path'] = $valuePathPrefix;
        if ($howManySegmentsToConsider < $valueSegmentsCount) {
            $prefixValue['type']='dir';
        }
        $spec = new Glob($boundedPrefixGlob);
        return $spec->isSatisfiedBy($prefixValue);
    }

    /** @inheritDoc */
    public function willBeSatisfiedByEverythingBelow(array $value): bool
    {
        if (!$this->canBeSatisfiedBySomethingBelow($value)) {
            return false;
        }
        if (null === $this->totalPrefix) {
            return false;
        }
        $spec = new Glob(rtrim($this->totalPrefix,'/').'/**/*');
        $terminatedValue = $value;
        $terminatedValue['path'] = rtrim($terminatedValue['path'],'/').'/x/x';
        return $spec->isSatisfiedBy($terminatedValue);
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			/**
6			* This file is part of phpDocumentor.
7			*
8			* For the full copyright and license information, please view the LICENSE
9			* file that was distributed with this source code.
10			*
11			* Many thanks to webmozart by providing the original code in webmozart/glob
12			*
13			* @link https://github.com/webmozart/glob/blob/master/src/Glob.php
14			* @link http://phpdoc.org
15			*/
16
17			namespace Flyfinder\Specification;
18
19			use Flyfinder\Path;
20			use InvalidArgumentException;
21			use function preg_match;
22			use function sprintf;
23			use function strlen;
24			use function strpos;
25
26			/**
27			* Glob specification class
28			*
29			* @psalm-immutable
30			*/
31			final class Glob extends CompositeSpecification
32			{
33			/** @var string */
34			private $regex;
35
36			/**
37			* The "static prefix" is the part of the glob up to the first wildcard "*".
38			* If the glob does not contain wildcards, the full glob is returned.
39			*
40			* @var string
41			*/
42			private $staticPrefix;
43
44			/**
45			* The "bounded prefix" is the part of the glob up to the first recursive wildcard "**".
46			* It is the longest prefix for which the number of directory segments in the partial match
47			* is known. If the glob does not contain the recursive wildcard "**", the full glob is returned.
48			* @var string
49			*/
50			private $boundedPrefix;
51
52			/**
53			* The "total prefix" is the part of the glob before the trailing catch-all wildcard sequence if the glob
54			* ends with one, otherwise null. It is needed for implementing the A-quantifier pruning hint.
55			* @var string
56			*/
57			private $totalPrefix;
58
59			public function __construct(string $glob)
60			{
61			$this->regex = self::toRegEx($glob);
62			$this->staticPrefix = self::getStaticPrefix($glob);
63			$this->boundedPrefix = self::getBoundedPrefix($glob);
64			$this->totalPrefix = self::getTotalPrefix($glob);
65			}
66
67			/**
68			* @inheritDoc
69			*/
70			public function isSatisfiedBy(array $value) : bool
71			{
72			//Flysystem paths are not absolute, so make it that way.
73			$path = '/' . $value['path'];
74			if (strpos($path, $this->staticPrefix) !== 0) {
75			return false;
76			}
77
78			if (preg_match($this->regex, $path)) {
79			return true;
80			}
81
82			return false;
83			}
84
85			/**
86			* Returns the static prefix of a glob.
87			*
88			* The "static prefix" is the part of the glob up to the first wildcard "*".
89			* If the glob does not contain wildcards, the full glob is returned.
90			*
91			* @param string $glob The canonical glob. The glob should contain forward
92			* slashes as directory separators only. It must not
93			* contain any "." or ".." segments.
94			*
95			* @return string The static prefix of the glob.
96			*
97			* @psalm-pure
98			*/
99			private static function getStaticPrefix(string $glob) : string
100			{
101			self::assertValidGlob($glob);
102			$prefix = '';
103			$length = strlen($glob);
104			for ($i = 0; $i < $length; ++$i) {
105			$c = $glob[$i];
106			switch ($c) {
107			case '/':
108			$prefix .= '/';
109			if (self::isRecursiveWildcard($glob, $i)) {
110			break 2;
111			}
112			break;
113			case '*':
114			case '?':
115			case '{':
116			case '[':
117			break 2;
118			case '\\':
119			self::scanBackslashSequence($prefix, $glob, $i);
120			break;
121			default:
122			$prefix .= $c;
123			break;
124			}
125			}
126			return $prefix;
127			}
128
129			private static function getBoundedPrefix(string $glob) : string
130			{
131			self::assertValidGlob($glob);
132			$prefix = '';
133			$length = strlen($glob);
134			for($i=0; $i < $length; ++$i) {
135			$c = $glob[$i];
136			switch ($c) {
137			case '/':
138			$prefix .= '/';
139			if(self::isRecursiveWildcard($glob, $i)) {
140			break 2;
141			}
142			break;
143			case '\\':
144			self::scanBackslashSequence($prefix, $glob, $i);
145			break;
146			default:
147			$prefix .= $c;
148			break;
149			}
150			}
151			return $prefix;
152			}
153
154			private static function getTotalPrefix(string $glob) : ?string
155			{
156			self::assertValidGlob($glob);
157			$matches=[];
158			return preg_match('~(?<!\\\\)/\\\\(?:/\\\\?)+$~', $glob, $matches)
159			? substr($glob,0,strlen($glob)-strlen($matches[0]))
160			: null;
161			}
162
163			private static function scanBackslashSequence(string &$prefix, string $glob, int &$i) : void
164			{
165			switch ($c = $glob[$i + 1] ?? '') {
166			case '*':
167			case '?':
168			case '{':
169			case '}':
170			case '[':
171			case ']':
172			case '-':
173			case '^':
174			case '$':
175			case '~':
176			case '\\':
177			$prefix .= $c;
178			++$i;
179			break;
180			default:
181			$prefix .= '\\';
182			}
183			}
184
185			/**
186			* @param string $glob
187			*/
188			private static function assertValidGlob(string $glob): void
189			{
190			if (strpos($glob, '/') !== 0 && strpos($glob, '://') === false) {
191			throw new InvalidArgumentException(sprintf(
192			'The glob "%s" is not absolute and not a URI.',
193			$glob
194			));
195			}
196			}
197
198			/**
199			* Checks if the current position the glob is start of a Recursive directory wildcard
200			*
201			* @psalm-pure
202			*/
203			private static function isRecursiveWildcard(string $glob, int $i) : bool
204			{
205			return isset($glob[$i + 3]) && $glob[$i + 1] . $glob[$i + 2] . $glob[$i + 3] === '**/';
206			}
207
208			/**
209			* Converts a glob to a regular expression.
210			*
211			* @param string $glob The canonical glob. The glob should contain forward
212			* slashes as directory separators only. It must not
213			* contain any "." or ".." segments.
214			*
215			* @return string The regular expression for matching the glob.
216			*
217			* @psalm-pure
218			*/
219			private static function toRegEx(string $glob) : string
220			{
221			$delimiter = '~';
222			$inSquare = false;
223			$curlyLevels = 0;
224			$regex = '';
225			$length = strlen($glob);
226			for ($i = 0; $i < $length; ++$i) {
227			$c = $glob[$i];
228			switch ($c) {
229			case '.':
230			case '(':
231			case ')':
232			case '\|':
233			case '+':
234			case '^':
235			case '$':
236			case $delimiter:
237			$regex .= '\\' . $c;
238			break;
239			case '/':
240			if (self::isRecursiveWildcard($glob, $i)) {
241			$regex .= '/([^/]+/)*';
242			$i += 3;
243			} else {
244			$regex .= '/';
245			}
246			break;
247			case '*':
248			$regex .= '[^/]*';
249			break;
250			case '?':
251			$regex .= '.';
252			break;
253			case '{':
254			$regex .= '(';
255			++$curlyLevels;
256			break;
257			case '}':
258			if ($curlyLevels > 0) {
259			$regex .= ')';
260			--$curlyLevels;
261			} else {
262			$regex .= '}';
263			}
264			break;
265			case ',':
266			$regex .= $curlyLevels > 0 ? '\|' : ',';
267			break;
268			case '[':
269			$regex .= '[';
270			$inSquare = true;
271			if (isset($glob[$i + 1]) && $glob[$i + 1] === '^') {
272			$regex .= '^';
273			++$i;
274			}
275			break;
276			case ']':
277			$regex .= $inSquare ? ']' : '\\]';
278			$inSquare = false;
279			break;
280			case '-':
281			$regex .= $inSquare ? '-' : '\\-';
282			break;
283			case '\\':
284			if (isset($glob[$i + 1])) {
285			switch ($glob[$i + 1]) {
286			case '*':
287			case '?':
288			case '{':
289			case '}':
290			case '[':
291			case ']':
292			case '-':
293			case '^':
294			case '$':
295			case '~':
296			case '\\':
297			$regex .= '\\' . $glob[$i + 1];
298			++$i;
299			break;
300			default:
301			$regex .= '\\\\';
302			}
303			}
304			break;
305			default:
306			$regex .= $c;
307			break;
308			}
309			}
310			if ($inSquare) {
311			throw new InvalidArgumentException(sprintf(
312			'Invalid glob: missing ] in %s',
313			$glob
314			));
315			}
316			if ($curlyLevels > 0) {
317			throw new InvalidArgumentException(sprintf(
318			'Invalid glob: missing } in %s',
319			$glob
320			));
321			}
322			return $delimiter . '^' . $regex . '$' . $delimiter;
323			}
324
325			/** @inheritDoc */
326			public function canBeSatisfiedBySomethingBelow(array $value): bool
327			{
328			$valueSegments = explode('/','/'.$value['path']);
329			$valueSegmentsCount = count($valueSegments);
330			$boundedPrefixGlobSegments = explode('/',rtrim($this->boundedPrefix,'/'));
331			$boundedPrefixGlobSegmentsCount = count($boundedPrefixGlobSegments);
332			$howManySegmentsToConsider = min($valueSegmentsCount,$boundedPrefixGlobSegmentsCount);
333			$boundedPrefixGlob = implode('/',array_slice($boundedPrefixGlobSegments, 0, $howManySegmentsToConsider));
334			$valuePathPrefix = implode('/',array_slice($valueSegments, 1, max($howManySegmentsToConsider-1,0)));
335			$prefixValue = $value;
336			$prefixValue['path'] = $valuePathPrefix;
337			if ($howManySegmentsToConsider < $valueSegmentsCount) {
338			$prefixValue['type']='dir';
339			}
340			$spec = new Glob($boundedPrefixGlob);
341			return $spec->isSatisfiedBy($prefixValue);
342			}
343
344			/** @inheritDoc */
345			public function willBeSatisfiedByEverythingBelow(array $value): bool
346			{
347			if (!$this->canBeSatisfiedBySomethingBelow($value)) {
348			return false;
349			}
350			if (null === $this->totalPrefix) {
351			return false;
352			}
353			$spec = new Glob(rtrim($this->totalPrefix,'/').'/*/');
354			$terminatedValue = $value;
355			$terminatedValue['path'] = rtrim($terminatedValue['path'],'/').'/x/x';
356			return $spec->isSatisfiedBy($terminatedValue);
357			}
358			}
359

phpDocumentor / FlyFinder

Pull Request — master (#15)

Glob::getStaticPrefix() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like