OverrideGraph::forPackages() - Code Metrics - Inspection of "Added checks for empty package files" - puli/manager - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — master (#39)

by Bernhard

created 2015-12-30 10:59 UTC

OverrideGraph::forPackages() C

↳ Parent: OverrideGraph

Complexity

Conditions	7
Paths	9

Size

Total Lines	31
Code Lines	15

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	18
CRAP Score	7

Importance

Changes	1
Bugs	0	Features	1

Metric	Value
c	1
b	0
f	1
dl	0
loc	31
ccs	18
cts	18
cp	1
rs	6.7273
cc	7
eloc	15
nc	9
nop	1
crap	7

<?php

/*
 * This file is part of the puli/manager package.
 *
 * (c) Bernhard Schussek <[email protected]>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace Puli\Manager\Conflict;

use Puli\Manager\Api\Package\PackageCollection;
use RuntimeException;

/**
 * A directed, acyclic graph of package names.
 *
 * Packages can be added with {@link addPackageName()}. Edges between these packages
 * can then be added using {@link addEdge()}. Both ends of an edge must have
 * been defined before the edge is added.
 *
 * ```php
 * $graph = new OverrideGraph();
 * $graph->addPackageName('acme/core');
 * $graph->addPackageName('acme/blog');
 * $graph->addPackageName('acme/blog-extension1');
 * $graph->addPackageName('acme/blog-extension2');
 * $graph->addEdge('acme/core', 'acme/blog');
 * $graph->addEdge('acme/blog', 'acme/blog-extension1');
 * $graph->addEdge('acme/blog', 'acme/blog-extension2');
 * $graph->addEdge('acme/blog-extension1', 'acme/blog-extension2');
 * ```
 *
 * You can use {@link getPath()} and {@link hasPath()} to check whether a path
 * exists from one package to the other:
 *
 * ```php
 * // ...
 *
 * $graph->hasPath('acme/blog', 'acme/blog-extension1');
 * // => true
 *
 * $graph->hasPath('acme/blog-extension1', 'acme/blog-extension2');
 * // => false
 *
 * $graph->getPath('acme/core', 'acme/blog-extension2');
 * // => array('acme/core', 'acme/blog', 'acme/blog-extension2')
 * ```
 *
 * With {@link getSortedPackageNames()}, you can sort the packages such that the
 * dependencies defined via the edges are respected:
 *
 * ```php
 * // ...
 *
 * $graph->getSortedPackageNames();
 * // => array('acme/core', 'acme/blog', 'acme/blog-extension1', 'acme/blog-extension2')
 * ```
 *
 * @since  1.0
 *
 * @author Bernhard Schussek <[email protected]>
 */
class OverrideGraph
{
    /**
     * Stores the names of all packages (vertices) as keys.
     *
     * @var array
     */
    private $packageNames = array();

    /**
     * Stores the edges in the keys of a multi-dimensional array.
     *
     * The first dimension stores the targets, the second dimension the origins
     * of the edges.
     *
     * @var array
     */
    private $edges = array();

    /**
     * Creates an override graph for the given packages.
     *
     * @param PackageCollection $packages The packages to load.
     *
     * @return static The created override graph.
     */
    public static function forPackages(PackageCollection $packages)
    {
        $graph = new static($packages->getPackageNames());

        foreach ($packages as $package) {
            if (null === $package->getPackageFile()) {
                continue;
            }

            foreach ($package->getPackageFile()->getOverriddenPackages() as $overriddenPackage) {
                if ($graph->hasPackageName($overriddenPackage)) {
                    $graph->addEdge($overriddenPackage, $package->getName());
                }
            }
        }

        // Make sure we have numeric, ascending keys here
        $packageOrder = array_values($packages->getRootPackage()->getPackageFile()->getOverrideOrder());

        // Each package overrides the previous one in the list
        for ($i = 1, $l = count($packageOrder); $i < $l; ++$i) {
            $overriddenPackage = $packageOrder[$i - 1];
            $overridingPackage = $packageOrder[$i];

            if ($graph->hasPackageName($overriddenPackage)) {
                $graph->addEdge($overriddenPackage, $overridingPackage);
            }
        }

        return $graph;
    }

    /**
     * Creates a new graph.
     *
     * @param string[] $packageNames The package names stored in the nodes of
     *                               the graph.
     */
    public function __construct(array $packageNames = array())
    {
        $this->addPackageNames($packageNames);
    }

    /**
     * Adds a package name to the graph.
     *
     * @param string $packageName The package name.
     *
     * @throws RuntimeException If the package name already exists.
     */
    public function addPackageName($packageName)
    {
        if (isset($this->packageNames[$packageName])) {
            throw new RuntimeException(sprintf(
                'The package "%s" was added to the graph twice.',
                $packageName
            ));
        }

        $this->packageNames[$packageName] = true;
        $this->edges[$packageName] = array();
    }

    /**
     * Adds a list of package names to the graph.
     *
     * @param string[] $packageNames The package names.
     *
     * @throws RuntimeException If a package name already exists.
     */
    public function addPackageNames(array $packageNames)
    {
        foreach ($packageNames as $packageName) {
            $this->addPackageName($packageName);
        }
    }

    /**
     * Returns whether a package name exists in the graph.
     *
     * @param string $packageName The package name.
     *
     * @return bool Whether the package name exists.
     */
    public function hasPackageName($packageName)
    {
        return isset($this->packageNames[$packageName]);
    }

    /**
     * Adds a directed edge from one to another package.
     *
     * @param string $from The start package name.
     * @param string $to   The end package name.
     *
     * @throws RuntimeException          If any of the packages does not exist in the
     *                                   graph. Each package must have been added first.
     * @throws CyclicDependencyException If adding the edge would create a cycle.
     */
    public function addEdge($from, $to)
    {
        if (!isset($this->packageNames[$from])) {
            throw new RuntimeException(sprintf(
                'The package "%s" does not exist in the graph.',
                $from
            ));
        }

        if (!isset($this->packageNames[$to])) {
            throw new RuntimeException(sprintf(
                'The package "%s" does not exist in the graph.',
                $to
            ));
        }

        if (null !== ($path = $this->getPath($to, $from))) {
            $last = array_pop($path);

            throw new CyclicDependencyException(sprintf(
                'A cyclic dependency was discovered between the packages "%s" '.
                'and "%s". Please check the "override" keys defined in these'.
                'packages.',
                implode('", "', $path),
                $last
            ));
        }

        $this->edges[$to][$from] = true;
    }

    public function removeEdge($from, $to)
    {
        unset($this->edges[$to][$from]);
    }

    /**
     * Returns whether an edge exists between two packages.
     *
     * @param string $from The start package name.
     * @param string $to   The end package name.
     *
     * @return bool Whether an edge exists from the origin to the target package.
     */
    public function hasEdge($from, $to)
    {
        return isset($this->edges[$to][$from]);
    }

    /**
     * Returns whether a path exists from one to another package.
     *
     * @param string $from The start package name.
     * @param string $to   The end package name.
     *
     * @return bool Whether a path exists from the origin to the target package.
     */
    public function hasPath($from, $to)
    {
        // does not exist in the graph
        if (!isset($this->edges[$to])) {
            return false;
        }

        // adjacent node
        if (isset($this->edges[$to][$from])) {
            return true;
        }

        // DFS
        foreach ($this->edges[$to] as $predecessor => $_) {
            if ($this->hasPath($from, $predecessor)) {
                return true;
            }
        }

        return false;
    }

    /**
     * Returns the path from one to another package.
     *
     * @param string $from The start package name.
     * @param string $to   The end package name.
     *
     * @return string[]|null The path of package names or `null`, if no path

     *                       was found.
     */
    public function getPath($from, $to)
    {
        if ($this->getPathDFS($from, $to, $reversePath)) {
            return array_reverse($reversePath);
        }

        return null;
    }

    /**
     * Returns all package names in the graph.
     *
     * @return array All package names in the graph.
     */
    public function getPackageNames()
    {
        return $this->packageNames;
    }

    /**
     * Sorts package names according to the defined edges.
     *
     * The names are sorted such that if two packages p1 and p2 have an edge
     * (p1, p2) in the graph, then p1 comes before p2 in the sorted set.
     *
     * If no package names are passed, all names are sorted.
     *
     * @param string[] $namesToSort The package names which should be sorted.
     *
     * @return string[] The sorted package names.
     *
     * @throws RuntimeException If any of the passed package names does not
     *                          exist in the graph.
     */
    public function getSortedPackageNames(array $namesToSort = array())
    {
        if (count($namesToSort) > 0) {
            $namesToSort = array_flip($namesToSort);

            foreach ($namesToSort as $package => $_) {
                if (!isset($this->packageNames[$package])) {
                    throw new RuntimeException(sprintf(
                        'The package "%s" does not exist in the graph.',
                        $package
                    ));
                }
            }
        } else {
            $namesToSort = $this->packageNames;
        }

        $sorted = array();

        // Do a topologic sort
        // Start with any package and process until no more are left
        while (false !== reset($namesToSort)) {
            $this->sortPackagesDFS(key($namesToSort), $namesToSort, $sorted);
        }

        return $sorted;
    }

    /**
     * Finds a path between packages using Depth-First Search.
     *
     * @param string $from        The start package name.
     * @param string $to          The end package name.
     * @param array  $reversePath The path in reverse order.
     *
     * @return bool Whether a path was found.
     */
    private function getPathDFS($from, $to, &$reversePath = array())

    {
        // does not exist in the graph
        if (!isset($this->edges[$to])) {
            return false;
        }

        $reversePath[] = $to;

        // adjacent node
        if (isset($this->edges[$to][$from])) {
            $reversePath[] = $from;

            return true;
        }

        // DFS
        foreach ($this->edges[$to] as $predecessor => $_) {
            if ($this->getPathDFS($from, $predecessor, $reversePath)) {
                return true;
            }
        }

        return false;
    }

    /**
     * Topologically sorts the given package name into the output array.
     *
     * The resulting array is sorted such that all predecessors of the package
     * come before the package (and their predecessors before them, and so on).
     *
     * @param string $currentName The current package name to sort.
     * @param array  $namesToSort The package names yet to be sorted.
     * @param array  $output      The output array.
     */
    private function sortPackagesDFS($currentName, array &$namesToSort, array &$output)

    {
        unset($namesToSort[$currentName]);

        // Before adding the package itself to the path, add all predecessors.
        // Do so recursively, then we make sure that each package is visited
        // in the path before any of its successors.
        foreach ($this->edges[$currentName] as $predecessor => $_) {
            // The package was already processed. Either the package is on the
            // path already, then we're good. Otherwise, we have a cycle.
            // However, addEdge() guarantees that the graph is cycle-free.
            if (isset($namesToSort[$predecessor])) {
                $this->sortPackagesDFS($predecessor, $namesToSort, $output);
            }
        }

        $output[] = $currentName;
    }
}


1		<?php
2
3		/*
4		* This file is part of the puli/manager package.
5		*
6		* (c) Bernhard Schussek <[email protected]>
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 Puli\Manager\Conflict;
13
14		use Puli\Manager\Api\Package\PackageCollection;
15		use RuntimeException;
16
17		/**
18		* A directed, acyclic graph of package names.
19		*
20		* Packages can be added with {@link addPackageName()}. Edges between these packages
21		* can then be added using {@link addEdge()}. Both ends of an edge must have
22		* been defined before the edge is added.
23		*
24		* ```php
25		* $graph = new OverrideGraph();
26		* $graph->addPackageName('acme/core');
27		* $graph->addPackageName('acme/blog');
28		* $graph->addPackageName('acme/blog-extension1');
29		* $graph->addPackageName('acme/blog-extension2');
30		* $graph->addEdge('acme/core', 'acme/blog');
31		* $graph->addEdge('acme/blog', 'acme/blog-extension1');
32		* $graph->addEdge('acme/blog', 'acme/blog-extension2');
33		* $graph->addEdge('acme/blog-extension1', 'acme/blog-extension2');
34		* ```
35		*
36		* You can use {@link getPath()} and {@link hasPath()} to check whether a path
37		* exists from one package to the other:
38		*
39		* ```php
40		* // ...
41		*
42		* $graph->hasPath('acme/blog', 'acme/blog-extension1');
43		* // => true
44		*
45		* $graph->hasPath('acme/blog-extension1', 'acme/blog-extension2');
46		* // => false
47		*
48		* $graph->getPath('acme/core', 'acme/blog-extension2');
49		* // => array('acme/core', 'acme/blog', 'acme/blog-extension2')
50		* ```
51		*
52		* With {@link getSortedPackageNames()}, you can sort the packages such that the
53		* dependencies defined via the edges are respected:
54		*
55		* ```php
56		* // ...
57		*
58		* $graph->getSortedPackageNames();
59		* // => array('acme/core', 'acme/blog', 'acme/blog-extension1', 'acme/blog-extension2')
60		* ```
61		*
62		* @since 1.0
63		*
64		* @author Bernhard Schussek <[email protected]>
65		*/
66		class OverrideGraph
67		{
68		/**
69		* Stores the names of all packages (vertices) as keys.
70		*
71		* @var array
72		*/
73		private $packageNames = array();
74
75		/**
76		* Stores the edges in the keys of a multi-dimensional array.
77		*
78		* The first dimension stores the targets, the second dimension the origins
79		* of the edges.
80		*
81		* @var array
82		*/
83		private $edges = array();
84
85		/**
86		* Creates an override graph for the given packages.
87		*
88		* @param PackageCollection $packages The packages to load.
89		*
90		* @return static The created override graph.
91		*/
92	62	public static function forPackages(PackageCollection $packages)
93		{
94	62	$graph = new static($packages->getPackageNames());
95
96	62	foreach ($packages as $package) {
97	62	if (null === $package->getPackageFile()) {
98	14	continue;
99	13	}
100	13
101	62	foreach ($package->getPackageFile()->getOverriddenPackages() as $overriddenPackage) {
102	62	if ($graph->hasPackageName($overriddenPackage)) {
103		$graph->addEdge($overriddenPackage, $package->getName());
104		}
105	62	}
106		}
107
108	62	// Make sure we have numeric, ascending keys here
109	1	$packageOrder = array_values($packages->getRootPackage()->getPackageFile()->getOverrideOrder());
110	1
111		// Each package overrides the previous one in the list
112	1	for ($i = 1, $l = count($packageOrder); $i < $l; ++$i) {
113	1	$overriddenPackage = $packageOrder[$i - 1];
114	1	$overridingPackage = $packageOrder[$i];
115	1
116		if ($graph->hasPackageName($overriddenPackage)) {
117	62	$graph->addEdge($overriddenPackage, $overridingPackage);
118		}
119		}
120
121		return $graph;
122		}
123
124		/**
125		* Creates a new graph.
126	101	*
127		* @param string[] $packageNames The package names stored in the nodes of
128	101	* the graph.
129	101	*/
130		public function __construct(array $packageNames = array())
131		{
132		$this->addPackageNames($packageNames);
133		}
134
135		/**
136		* Adds a package name to the graph.
137		*
138	100	* @param string $packageName The package name.
139		*
140	100	* @throws RuntimeException If the package name already exists.
141	1	*/
142	1	public function addPackageName($packageName)
143		{
144	1	if (isset($this->packageNames[$packageName])) {
145		throw new RuntimeException(sprintf(
146		'The package "%s" was added to the graph twice.',
147	100	$packageName
148	100	));
149	100	}
150
151		$this->packageNames[$packageName] = true;
152		$this->edges[$packageName] = array();
153		}
154
155		/**
156		* Adds a list of package names to the graph.
157		*
158	101	* @param string[] $packageNames The package names.
159		*
160	101	* @throws RuntimeException If a package name already exists.
161	74	*/
162	101	public function addPackageNames(array $packageNames)
163	101	{
164		foreach ($packageNames as $packageName) {
165		$this->addPackageName($packageName);
166		}
167		}
168
169		/**
170		* Returns whether a package name exists in the graph.
171		*
172	18	* @param string $packageName The package name.
173		*
174	18	* @return bool Whether the package name exists.
175		*/
176		public function hasPackageName($packageName)
177		{
178		return isset($this->packageNames[$packageName]);
179		}
180
181		/**
182		* Adds a directed edge from one to another package.
183		*
184		* @param string $from The start package name.
185		* @param string $to The end package name.
186		*
187	46	* @throws RuntimeException If any of the packages does not exist in the
188		* graph. Each package must have been added first.
189	46	* @throws CyclicDependencyException If adding the edge would create a cycle.
190	1	*/
191	1	public function addEdge($from, $to)
192		{
193	1	if (!isset($this->packageNames[$from])) {
194		throw new RuntimeException(sprintf(
195		'The package "%s" does not exist in the graph.',
196	45	$from
197	1	));
198	1	}
199
200	1	if (!isset($this->packageNames[$to])) {
201		throw new RuntimeException(sprintf(
202		'The package "%s" does not exist in the graph.',
203	44	$to
204	1	));
205		}
206	1
207		if (null !== ($path = $this->getPath($to, $from))) {
208	1	$last = array_pop($path);
209	1
210	1	throw new CyclicDependencyException(sprintf(
211		'A cyclic dependency was discovered between the packages "%s" '.
212	1	'and "%s". Please check the "override" keys defined in these'.
213		'packages.',
214		implode('", "', $path),
215	44	$last
216	44	));
217		}
218	2
219		$this->edges[$to][$from] = true;
220	2	}
221	2
222		public function removeEdge($from, $to)
223		{
224		unset($this->edges[$to][$from]);
225		}
226
227		/**
228		* Returns whether an edge exists between two packages.
229		*
230		* @param string $from The start package name.
231	39	* @param string $to The end package name.
232		*
233	39	* @return bool Whether an edge exists from the origin to the target package.
234		*/
235		public function hasEdge($from, $to)
236		{
237		return isset($this->edges[$to][$from]);
238		}
239
240		/**
241		* Returns whether a path exists from one to another package.
242		*
243		* @param string $from The start package name.
244	9	* @param string $to The end package name.
245		*
246		* @return bool Whether a path exists from the origin to the target package.
247	9	*/
248	1	public function hasPath($from, $to)
249		{
250		// does not exist in the graph
251		if (!isset($this->edges[$to])) {
252	8	return false;
253	2	}
254
255		// adjacent node
256		if (isset($this->edges[$to][$from])) {
257	7	return true;
258	2	}
259	1
260		// DFS
261	6	foreach ($this->edges[$to] as $predecessor => $_) {
262		if ($this->hasPath($from, $predecessor)) {
263	6	return true;
264		}
265		}
266
267		return false;
268		}
269
270		/**
271		* Returns the path from one to another package.
272		*
273		* @param string $from The start package name.
274		* @param string $to The end package name.
275	44	*
276		* @return string[]\|null The path of package names or `null`, if no path
		0 ignored issues – show Documentation introduced 2015-12-06 22:18 UTC by Report Bug Copy Issue Report Should the return type not be `array\|null`? Also, consider making the array more specific, something like `array<String>`, or `String[]`. This check compares the return type specified in the `@return` annotation of a function or method doc comment with the types returned by the function and raises an issue if they mismatch. If the return type contains the type array, this check recommends the use of a more specific type like `String[]` or `array<String>`. Loading history...
277	44	* was found.
278	3	*/
279		public function getPath($from, $to)
280		{
281	44	if ($this->getPathDFS($from, $to, $reversePath)) {
282		return array_reverse($reversePath);
283		}
284
285		return null;
286		}
287
288		/**
289		* Returns all package names in the graph.
290		*
291		* @return array All package names in the graph.
292		*/
293		public function getPackageNames()
294		{
295		return $this->packageNames;
296		}
297
298		/**
299		* Sorts package names according to the defined edges.
300		*
301		* The names are sorted such that if two packages p1 and p2 have an edge
302		* (p1, p2) in the graph, then p1 comes before p2 in the sorted set.
303		*
304		* If no package names are passed, all names are sorted.
305		*
306		* @param string[] $namesToSort The package names which should be sorted.
307		*
308		* @return string[] The sorted package names.
309	55	*
310		* @throws RuntimeException If any of the passed package names does not
311	55	* exist in the graph.
312	54	*/
313		public function getSortedPackageNames(array $namesToSort = array())
314	54	{
315	54	if (count($namesToSort) > 0) {
316	1	$namesToSort = array_flip($namesToSort);
317	1
318		foreach ($namesToSort as $package => $_) {
319	1	if (!isset($this->packageNames[$package])) {
320		throw new RuntimeException(sprintf(
321	53	'The package "%s" does not exist in the graph.',
322	53	$package
323	1	));
324		}
325		}
326	54	} else {
327		$namesToSort = $this->packageNames;
328		}
329
330	54	$sorted = array();
331	54
332	54	// Do a topologic sort
333		// Start with any package and process until no more are left
334	54	while (false !== reset($namesToSort)) {
335		$this->sortPackagesDFS(key($namesToSort), $namesToSort, $sorted);
336		}
337
338		return $sorted;
339		}
340
341		/**
342		* Finds a path between packages using Depth-First Search.
343		*
344		* @param string $from The start package name.
345		* @param string $to The end package name.
346	44	* @param array $reversePath The path in reverse order.
347		*
348		* @return bool Whether a path was found.
349	44	*/
350	1	private function getPathDFS($from, $to, &$reversePath = array())
		0 ignored issues – show Coding Style introduced 2015-12-06 22:18 UTC by Report Bug Copy Issue Report This method is not in camel caps format. This check looks for method names that are not written in camelCase. In camelCase names are written without any punctuation, the start of each new word being marked by a capital letter. Thus the name database connection seeker becomes `databaseConnectionSeeker`. Loading history...
351		{
352		// does not exist in the graph
353	44	if (!isset($this->edges[$to])) {
354		return false;
355		}
356	44
357	3	$reversePath[] = $to;
358
359	3	// adjacent node
360		if (isset($this->edges[$to][$from])) {
361		$reversePath[] = $from;
362
363	44	return true;
364	23	}
365	1
366		// DFS
367	44	foreach ($this->edges[$to] as $predecessor => $_) {
368		if ($this->getPathDFS($from, $predecessor, $reversePath)) {
369	44	return true;
370		}
371		}
372
373		return false;
374		}
375
376		/**
377		* Topologically sorts the given package name into the output array.
378		*
379		* The resulting array is sorted such that all predecessors of the package
380		* come before the package (and their predecessors before them, and so on).
381		*
382	54	* @param string $currentName The current package name to sort.
383		* @param array $namesToSort The package names yet to be sorted.
384	54	* @param array $output The output array.
385		*/
386		private function sortPackagesDFS($currentName, array &$namesToSort, array &$output)
		0 ignored issues – show Coding Style introduced 2015-12-06 22:18 UTC by Report Bug Copy Issue Report This method is not in camel caps format. This check looks for method names that are not written in camelCase. In camelCase names are written without any punctuation, the start of each new word being marked by a capital letter. Thus the name database connection seeker becomes `databaseConnectionSeeker`. Loading history...
387		{
388		unset($namesToSort[$currentName]);
389	54
390		// Before adding the package itself to the path, add all predecessors.
391		// Do so recursively, then we make sure that each package is visited
392		// in the path before any of its successors.
393	24	foreach ($this->edges[$currentName] as $predecessor => $_) {
394	9	// The package was already processed. Either the package is on the
395	9	// path already, then we're good. Otherwise, we have a cycle.
396	54	// However, addEdge() guarantees that the graph is cycle-free.
397		if (isset($namesToSort[$predecessor])) {
398	54	$this->sortPackagesDFS($predecessor, $namesToSort, $output);
399	54	}
400		}
401
402		$output[] = $currentName;
403		}
404		}
405

puli / manager

Pull Request — master (#39)

OverrideGraph::forPackages() C

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like