OverrideGraph::getSortedPackageNames() - Code Metrics - Inspection of "Merge pull request #41 from webmozart/package-orde..." - puli/manager - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 2aa028...155152 )

by Bernhard

created 2016-01-05 11:44 UTC

OverrideGraph::getSortedPackageNames() B

↳ Parent: OverrideGraph

Complexity

Conditions	5
Paths	5

Size

Total Lines	27
Code Lines	14

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	16
CRAP Score	5

Metric	Value
dl	0
loc	27
ccs	16
cts	16
cp	1
rs	8.439
cc	5
eloc	14
nc	5
nop	1
crap	5

<?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());
                }
            }
        }

        // Do we have a root package?
        if (null === $packages->getRootPackage()) {
            return $graph;
        }

        // 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	93	public static function forPackages(PackageCollection $packages)
93		{
94	93	$graph = new static($packages->getPackageNames());
95
96	93	foreach ($packages as $package) {
97	93	if (null === $package->getPackageFile()) {
98	2	continue;
99		}
100
101	93	foreach ($package->getPackageFile()->getOverriddenPackages() as $overriddenPackage) {
102	35	if ($graph->hasPackageName($overriddenPackage)) {
103	34	$graph->addEdge($overriddenPackage, $package->getName());
104	34	}
105	93	}
106	93	}
107
108		// Do we have a root package?
109	93	if (null === $packages->getRootPackage()) {
110	20	return $graph;
111		}
112
113		// Make sure we have numeric, ascending keys here
114	73	$packageOrder = array_values($packages->getRootPackage()->getPackageFile()->getOverrideOrder());
115
116		// Each package overrides the previous one in the list
117	73	for ($i = 1, $l = count($packageOrder); $i < $l; ++$i) {
118	1	$overriddenPackage = $packageOrder[$i - 1];
119	1	$overridingPackage = $packageOrder[$i];
120
121	1	if ($graph->hasPackageName($overriddenPackage)) {
122	1	$graph->addEdge($overriddenPackage, $overridingPackage);
123	1	}
124	1	}
125
126	73	return $graph;
127		}
128
129		/**
130		* Creates a new graph.
131		*
132		* @param string[] $packageNames The package names stored in the nodes of
133		* the graph.
134		*/
135	132	public function __construct(array $packageNames = array())
136		{
137	132	$this->addPackageNames($packageNames);
138	132	}
139
140		/**
141		* Adds a package name to the graph.
142		*
143		* @param string $packageName The package name.
144		*
145		* @throws RuntimeException If the package name already exists.
146		*/
147	131	public function addPackageName($packageName)
148		{
149	131	if (isset($this->packageNames[$packageName])) {
150	1	throw new RuntimeException(sprintf(
151	1	'The package "%s" was added to the graph twice.',
152		$packageName
153	1	));
154		}
155
156	131	$this->packageNames[$packageName] = true;
157	131	$this->edges[$packageName] = array();
158	131	}
159
160		/**
161		* Adds a list of package names to the graph.
162		*
163		* @param string[] $packageNames The package names.
164		*
165		* @throws RuntimeException If a package name already exists.
166		*/
167	132	public function addPackageNames(array $packageNames)
168		{
169	132	foreach ($packageNames as $packageName) {
170	105	$this->addPackageName($packageName);
171	132	}
172	132	}
173
174		/**
175		* Returns whether a package name exists in the graph.
176		*
177		* @param string $packageName The package name.
178		*
179		* @return bool Whether the package name exists.
180		*/
181	40	public function hasPackageName($packageName)
182		{
183	40	return isset($this->packageNames[$packageName]);
184		}
185
186		/**
187		* Adds a directed edge from one to another package.
188		*
189		* @param string $from The start package name.
190		* @param string $to The end package name.
191		*
192		* @throws RuntimeException If any of the packages does not exist in the
193		* graph. Each package must have been added first.
194		* @throws CyclicDependencyException If adding the edge would create a cycle.
195		*/
196	67	public function addEdge($from, $to)
197		{
198	67	if (!isset($this->packageNames[$from])) {
199	1	throw new RuntimeException(sprintf(
200	1	'The package "%s" does not exist in the graph.',
201		$from
202	1	));
203		}
204
205	66	if (!isset($this->packageNames[$to])) {
206	1	throw new RuntimeException(sprintf(
207	1	'The package "%s" does not exist in the graph.',
208		$to
209	1	));
210		}
211
212	65	if (null !== ($path = $this->getPath($to, $from))) {
213	1	$last = array_pop($path);
214
215	1	throw new CyclicDependencyException(sprintf(
216		'A cyclic dependency was discovered between the packages "%s" '.
217	1	'and "%s". Please check the "override" keys defined in these '.
218	1	'packages.',
219	1	implode('", "', $path),
220		$last
221	1	));
222		}
223
224	65	$this->edges[$to][$from] = true;
225	65	}
226
227	2	public function removeEdge($from, $to)
228		{
229	2	unset($this->edges[$to][$from]);
230	2	}
231
232		/**
233		* Returns whether an edge exists between two packages.
234		*
235		* @param string $from The start package name.
236		* @param string $to The end package name.
237		*
238		* @return bool Whether an edge exists from the origin to the target package.
239		*/
240	40	public function hasEdge($from, $to)
241		{
242	40	return isset($this->edges[$to][$from]);
243		}
244
245		/**
246		* Returns whether a path exists from one to another package.
247		*
248		* @param string $from The start package name.
249		* @param string $to The end package name.
250		*
251		* @return bool Whether a path exists from the origin to the target package.
252		*/
253	9	public function hasPath($from, $to)
254		{
255		// does not exist in the graph
256	9	if (!isset($this->edges[$to])) {
257	1	return false;
258		}
259
260		// adjacent node
261	8	if (isset($this->edges[$to][$from])) {
262	2	return true;
263		}
264
265		// DFS
266	7	foreach ($this->edges[$to] as $predecessor => $_) {
267	2	if ($this->hasPath($from, $predecessor)) {
268	1	return true;
269		}
270	6	}
271
272	6	return false;
273		}
274
275		/**
276		* Returns the path from one to another package.
277		*
278		* @param string $from The start package name.
279		* @param string $to The end package name.
280		*
281		* @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...
282		* was found.
283		*/
284	65	public function getPath($from, $to)
285		{
286	65	if ($this->getPathDFS($from, $to, $reversePath)) {
287	3	return array_reverse($reversePath);
288		}
289
290	65	return null;
291		}
292
293		/**
294		* Returns all package names in the graph.
295		*
296		* @return array All package names in the graph.
297		*/
298		public function getPackageNames()
299		{
300		return $this->packageNames;
301		}
302
303		/**
304		* Sorts package names according to the defined edges.
305		*
306		* The names are sorted such that if two packages p1 and p2 have an edge
307		* (p1, p2) in the graph, then p1 comes before p2 in the sorted set.
308		*
309		* If no package names are passed, all names are sorted.
310		*
311		* @param string[] $namesToSort The package names which should be sorted.
312		*
313		* @return string[] The sorted package names.
314		*
315		* @throws RuntimeException If any of the passed package names does not
316		* exist in the graph.
317		*/
318	83	public function getSortedPackageNames(array $namesToSort = array())
319		{
320	83	if (count($namesToSort) > 0) {
321	54	$namesToSort = array_flip($namesToSort);
322
323	54	foreach ($namesToSort as $package => $_) {
324	54	if (!isset($this->packageNames[$package])) {
325	1	throw new RuntimeException(sprintf(
326	1	'The package "%s" does not exist in the graph.',
327		$package
328	1	));
329		}
330	53	}
331	53	} else {
332	29	$namesToSort = $this->packageNames;
333		}
334
335	82	$sorted = array();
336
337		// Do a topologic sort
338		// Start with any package and process until no more are left
339	82	while (false !== reset($namesToSort)) {
340	82	$this->sortPackagesDFS(key($namesToSort), $namesToSort, $sorted);
341	82	}
342
343	82	return $sorted;
344		}
345
346		/**
347		* Finds a path between packages using Depth-First Search.
348		*
349		* @param string $from The start package name.
350		* @param string $to The end package name.
351		* @param array $reversePath The path in reverse order.
352		*
353		* @return bool Whether a path was found.
354		*/
355	65	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...
356		{
357		// does not exist in the graph
358	65	if (!isset($this->edges[$to])) {
359	1	return false;
360		}
361
362	65	$reversePath[] = $to;
363
364		// adjacent node
365	65	if (isset($this->edges[$to][$from])) {
366	3	$reversePath[] = $from;
367
368	3	return true;
369		}
370
371		// DFS
372	65	foreach ($this->edges[$to] as $predecessor => $_) {
373	44	if ($this->getPathDFS($from, $predecessor, $reversePath)) {
374	1	return true;
375		}
376	65	}
377
378	65	return false;
379		}
380
381		/**
382		* Topologically sorts the given package name into the output array.
383		*
384		* The resulting array is sorted such that all predecessors of the package
385		* come before the package (and their predecessors before them, and so on).
386		*
387		* @param string $currentName The current package name to sort.
388		* @param array $namesToSort The package names yet to be sorted.
389		* @param array $output The output array.
390		*/
391	82	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...
392		{
393	82	unset($namesToSort[$currentName]);
394
395		// Before adding the package itself to the path, add all predecessors.
396		// Do so recursively, then we make sure that each package is visited
397		// in the path before any of its successors.
398	82	foreach ($this->edges[$currentName] as $predecessor => $_) {
399		// The package was already processed. Either the package is on the
400		// path already, then we're good. Otherwise, we have a cycle.
401		// However, addEdge() guarantees that the graph is cycle-free.
402	44	if (isset($namesToSort[$predecessor])) {
403	29	$this->sortPackagesDFS($predecessor, $namesToSort, $output);
404	29	}
405	82	}
406
407	82	$output[] = $currentName;
408	82	}
409		}
410

puli / manager

Push — master ( 2aa028...155152 )

OverrideGraph::getSortedPackageNames() B

Complexity

Size

Duplication

Code Coverage

Duplication Side-by-Side

Filter issues like