OverrideGraph::forPackages() - Code Metrics - Inspection of "Merge pull request #39 from webmozart/fix-empty-pa..." - puli/manager - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( fa0673...7f3713 )

by Bernhard

created 2016-01-04 12:29 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	20
CRAP Score	7

Importance

Changes	1
Bugs	0	Features	1

Metric	Value
c	1
b	0
f	1
dl	0
loc	31
ccs	20
cts	20
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	65	public static function forPackages(PackageCollection $packages)
93		{
94	65	$graph = new static($packages->getPackageNames());
95
96	65	foreach ($packages as $package) {
97	65	if (null === $package->getPackageFile()) {
98	2	continue;
99		}
100
101	65	foreach ($package->getPackageFile()->getOverriddenPackages() as $overriddenPackage) {
102	15	if ($graph->hasPackageName($overriddenPackage)) {
103	14	$graph->addEdge($overriddenPackage, $package->getName());
104	14	}
105	65	}
106	65	}
107
108		// Make sure we have numeric, ascending keys here
109	65	$packageOrder = array_values($packages->getRootPackage()->getPackageFile()->getOverrideOrder());
110
111		// Each package overrides the previous one in the list
112	65	for ($i = 1, $l = count($packageOrder); $i < $l; ++$i) {
113	1	$overriddenPackage = $packageOrder[$i - 1];
114	1	$overridingPackage = $packageOrder[$i];
115
116	1	if ($graph->hasPackageName($overriddenPackage)) {
117	1	$graph->addEdge($overriddenPackage, $overridingPackage);
118	1	}
119	1	}
120
121	65	return $graph;
122		}
123
124		/**
125		* Creates a new graph.
126		*
127		* @param string[] $packageNames The package names stored in the nodes of
128		* the graph.
129		*/
130	104	public function __construct(array $packageNames = array())
131		{
132	104	$this->addPackageNames($packageNames);
133	104	}
134
135		/**
136		* Adds a package name to the graph.
137		*
138		* @param string $packageName The package name.
139		*
140		* @throws RuntimeException If the package name already exists.
141		*/
142	103	public function addPackageName($packageName)
143		{
144	103	if (isset($this->packageNames[$packageName])) {
145	1	throw new RuntimeException(sprintf(
146	1	'The package "%s" was added to the graph twice.',
147		$packageName
148	1	));
149		}
150
151	103	$this->packageNames[$packageName] = true;
152	103	$this->edges[$packageName] = array();
153	103	}
154
155		/**
156		* Adds a list of package names to the graph.
157		*
158		* @param string[] $packageNames The package names.
159		*
160		* @throws RuntimeException If a package name already exists.
161		*/
162	104	public function addPackageNames(array $packageNames)
163		{
164	104	foreach ($packageNames as $packageName) {
165	77	$this->addPackageName($packageName);
166	104	}
167	104	}
168
169		/**
170		* Returns whether a package name exists in the graph.
171		*
172		* @param string $packageName The package name.
173		*
174		* @return bool Whether the package name exists.
175		*/
176	20	public function hasPackageName($packageName)
177		{
178	20	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		* @throws RuntimeException If any of the packages does not exist in the
188		* graph. Each package must have been added first.
189		* @throws CyclicDependencyException If adding the edge would create a cycle.
190		*/
191	47	public function addEdge($from, $to)
192		{
193	47	if (!isset($this->packageNames[$from])) {
194	1	throw new RuntimeException(sprintf(
195	1	'The package "%s" does not exist in the graph.',
196		$from
197	1	));
198		}
199
200	46	if (!isset($this->packageNames[$to])) {
201	1	throw new RuntimeException(sprintf(
202	1	'The package "%s" does not exist in the graph.',
203		$to
204	1	));
205		}
206
207	45	if (null !== ($path = $this->getPath($to, $from))) {
208	1	$last = array_pop($path);
209
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	1	'packages.',
214	1	implode('", "', $path),
215		$last
216	1	));
217		}
218
219	45	$this->edges[$to][$from] = true;
220	45	}
221
222	2	public function removeEdge($from, $to)
223		{
224	2	unset($this->edges[$to][$from]);
225	2	}
226
227		/**
228		* Returns whether an edge exists between two packages.
229		*
230		* @param string $from The start package name.
231		* @param string $to The end package name.
232		*
233		* @return bool Whether an edge exists from the origin to the target package.
234		*/
235	40	public function hasEdge($from, $to)
236		{
237	40	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		* @param string $to The end package name.
245		*
246		* @return bool Whether a path exists from the origin to the target package.
247		*/
248	9	public function hasPath($from, $to)
249		{
250		// does not exist in the graph
251	9	if (!isset($this->edges[$to])) {
252	1	return false;
253		}
254
255		// adjacent node
256	8	if (isset($this->edges[$to][$from])) {
257	2	return true;
258		}
259
260		// DFS
261	7	foreach ($this->edges[$to] as $predecessor => $_) {
262	2	if ($this->hasPath($from, $predecessor)) {
263	1	return true;
264		}
265	6	}
266
267	6	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		*
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		* was found.
278		*/
279	45	public function getPath($from, $to)
280		{
281	45	if ($this->getPathDFS($from, $to, $reversePath)) {
282	3	return array_reverse($reversePath);
283		}
284
285	45	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		*
310		* @throws RuntimeException If any of the passed package names does not
311		* exist in the graph.
312		*/
313	55	public function getSortedPackageNames(array $namesToSort = array())
314		{
315	55	if (count($namesToSort) > 0) {
316	54	$namesToSort = array_flip($namesToSort);
317
318	54	foreach ($namesToSort as $package => $_) {
319	54	if (!isset($this->packageNames[$package])) {
320	1	throw new RuntimeException(sprintf(
321	1	'The package "%s" does not exist in the graph.',
322		$package
323	1	));
324		}
325	53	}
326	53	} else {
327	1	$namesToSort = $this->packageNames;
328		}
329
330	54	$sorted = array();
331
332		// Do a topologic sort
333		// Start with any package and process until no more are left
334	54	while (false !== reset($namesToSort)) {
335	54	$this->sortPackagesDFS(key($namesToSort), $namesToSort, $sorted);
336	54	}
337
338	54	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		* @param array $reversePath The path in reverse order.
347		*
348		* @return bool Whether a path was found.
349		*/
350	45	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	45	if (!isset($this->edges[$to])) {
354	1	return false;
355		}
356
357	45	$reversePath[] = $to;
358
359		// adjacent node
360	45	if (isset($this->edges[$to][$from])) {
361	3	$reversePath[] = $from;
362
363	3	return true;
364		}
365
366		// DFS
367	45	foreach ($this->edges[$to] as $predecessor => $_) {
368	24	if ($this->getPathDFS($from, $predecessor, $reversePath)) {
369	1	return true;
370		}
371	45	}
372
373	45	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		* @param string $currentName The current package name to sort.
383		* @param array $namesToSort The package names yet to be sorted.
384		* @param array $output The output array.
385		*/
386	54	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	54	unset($namesToSort[$currentName]);
389
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	54	foreach ($this->edges[$currentName] as $predecessor => $_) {
394		// The package was already processed. Either the package is on the
395		// path already, then we're good. Otherwise, we have a cycle.
396		// However, addEdge() guarantees that the graph is cycle-free.
397	24	if (isset($namesToSort[$predecessor])) {
398	9	$this->sortPackagesDFS($predecessor, $namesToSort, $output);
399	9	}
400	54	}
401
402	54	$output[] = $currentName;
403	54	}
404		}
405

puli / manager

Push — master ( fa0673...7f3713 )

OverrideGraph::forPackages() C

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like