OverrideGraph::addPackageName() - Code Metrics - Inspection of "Added GeneratedPuliFactory::getPackageOrder()" - puli/manager - Measure and Improve Code Quality continuously with Scrutinizer

Failed Conditions

Pull Request — master (#41)

by Bernhard

created 2016-01-04 13:44 UTC

OverrideGraph::addPackageName() A

↳ Parent: OverrideGraph

Complexity

Conditions	2
Paths	2

Size

Total Lines	12
Code Lines	7

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	8
CRAP Score	2

Metric	Value
dl	0
loc	12
ccs	8
cts	8
cp	1
rs	9.4286
cc	2
eloc	7
nc	2
nop	1
crap	2

<?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	84	public static function forPackages(PackageCollection $packages)
93		{
94	84	$graph = new static($packages->getPackageNames());
95
96	84	foreach ($packages as $package) {
97	84	if (null === $package->getPackageFile()) {
98	2	continue;
99		}
100
101	84	foreach ($package->getPackageFile()->getOverriddenPackages() as $overriddenPackage) {
102	34	if ($graph->hasPackageName($overriddenPackage)) {
103	33	$graph->addEdge($overriddenPackage, $package->getName());
104	33	}
105	84	}
106	84	}
107
108		// Do we have a root package?
109	84	if (null === $packages->getRootPackage()) {
110	19	return $graph;
111		}
112
113		// Make sure we have numeric, ascending keys here
114	65	$packageOrder = array_values($packages->getRootPackage()->getPackageFile()->getOverrideOrder());
115
116		// Each package overrides the previous one in the list
117	65	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	65	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	123	public function __construct(array $packageNames = array())
136		{
137	123	$this->addPackageNames($packageNames);
138	123	}
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	122	public function addPackageName($packageName)
148		{
149	122	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	122	$this->packageNames[$packageName] = true;
157	122	$this->edges[$packageName] = array();
158	122	}
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	123	public function addPackageNames(array $packageNames)
168		{
169	123	foreach ($packageNames as $packageName) {
170	96	$this->addPackageName($packageName);
171	123	}
172	123	}
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	39	public function hasPackageName($packageName)
182		{
183	39	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	66	public function addEdge($from, $to)
197		{
198	66	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	65	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	64	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	64	$this->edges[$to][$from] = true;
225	64	}
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	64	public function getPath($from, $to)
285		{
286	64	if ($this->getPathDFS($from, $to, $reversePath)) {
287	3	return array_reverse($reversePath);
288		}
289
290	64	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	74	public function getSortedPackageNames(array $namesToSort = array())
319		{
320	74	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	20	$namesToSort = $this->packageNames;
333		}
334
335	73	$sorted = array();
336
337		// Do a topologic sort
338		// Start with any package and process until no more are left
339	73	while (false !== reset($namesToSort)) {
340	73	$this->sortPackagesDFS(key($namesToSort), $namesToSort, $sorted);
341	73	}
342
343	73	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	64	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	64	if (!isset($this->edges[$to])) {
359	1	return false;
360		}
361
362	64	$reversePath[] = $to;
363
364		// adjacent node
365	64	if (isset($this->edges[$to][$from])) {
366	3	$reversePath[] = $from;
367
368	3	return true;
369		}
370
371		// DFS
372	64	foreach ($this->edges[$to] as $predecessor => $_) {
373	43	if ($this->getPathDFS($from, $predecessor, $reversePath)) {
374	1	return true;
375		}
376	64	}
377
378	64	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	73	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	73	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	73	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	43	if (isset($namesToSort[$predecessor])) {
403	28	$this->sortPackagesDFS($predecessor, $namesToSort, $output);
404	28	}
405	73	}
406
407	73	$output[] = $currentName;
408	73	}
409		}
410

puli / manager

Pull Request — master (#41)

OverrideGraph::addPackageName() A

Complexity

Size

Duplication

Code Coverage

Duplication Side-by-Side

Filter issues like