DependencyGraph::getModuleNames() - Code Metrics - Inspection of "Merge pull request #53 from webmozart/rename-confi..." - puli/manager - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( e3306a...3ebd86 )

by Bernhard

created 2016-02-01 16:55 UTC

DependencyGraph::getModuleNames() A

↳ Parent: DependencyGraph

Complexity

Conditions	1
Paths	1

Size

Total Lines	4
Code Lines	2

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	0
CRAP Score	2

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
c	1
b	0
f	0
dl	0
loc	4
ccs	0
cts	2
cp	0
rs	10
cc	1
eloc	2
nc	1
nop	0
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\Module\ModuleList;
use RuntimeException;

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

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

    /**
     * Creates an override graph for the given modules.
     *
     * @param ModuleList $modules The modules to load.
     *
     * @return static The created override graph.
     */
    public static function forModules(ModuleList $modules)
    {
        $graph = new static($modules->getModuleNames());

        foreach ($modules as $module) {
            if (null === $module->getModuleFile()) {
                continue;
            }

            foreach ($module->getModuleFile()->getDependencies() as $dependency) {
                if ($graph->hasModuleName($dependency)) {
                    $graph->addDependency($module->getName(), $dependency);
                }
            }
        }

        // Do we have a root module?
        if (null === $modules->getRootModule()) {
            return $graph;
        }

        // Make sure we have numeric, ascending keys here
        $moduleOrder = array_values($modules->getRootModule()->getModuleFile()->getModuleOrder());

        // Each module overrides the previous one in the list
        for ($i = 1, $l = count($moduleOrder); $i < $l; ++$i) {
            $dependency = $moduleOrder[$i - 1];
            $moduleName = $moduleOrder[$i];

            if ($graph->hasModuleName($dependency)) {
                $graph->addDependency($moduleName, $dependency);
            }
        }

        return $graph;
    }

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

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

        $this->moduleNames[$moduleName] = true;
        $this->dependencies[$moduleName] = array();
    }

    /**
     * Adds a list of module names to the graph.
     *
     * @param string[] $moduleNames The module names.
     *
     * @throws RuntimeException If a module name already exists.
     */
    public function addModuleNames(array $moduleNames)
    {
        foreach ($moduleNames as $moduleName) {
            $this->addModuleName($moduleName);
        }
    }

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

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

    /**
     * Returns the sorted module names.
     *
     * The names are sorted such that if a module m1 depends on a module m2,
     * then m2 comes before m1 in the sorted set.
     *
     * If module names are passed, only those module names are sorted. Otherwise
     * all module names are sorted.
     *
     * @param string[] $namesToSort The module names which should be sorted.
     *
     * @return string[] The sorted module names.
     *
     * @throws RuntimeException If any of the passed module names does not
     *                          exist in the graph.
     */
    public function getSortedModuleNames(array $namesToSort = array())
    {
        if (count($namesToSort) > 0) {
            $namesToSort = array_flip($namesToSort);

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

        $sorted = array();

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

        return $sorted;
    }

    /**
     * Adds a dependency from one to another module.
     *
     * @param string $moduleName The module name.
     * @param string $dependency The name of the dependency.
     */
    public function addDependency($moduleName, $dependency)
    {
        if (!isset($this->moduleNames[$dependency])) {
            throw new RuntimeException(sprintf(
                'The module "%s" does not exist in the graph.',
                $dependency
            ));
        }

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

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

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

        $this->dependencies[$moduleName][$dependency] = true;
    }

    /**
     * Removes a dependency from one to another module.
     *
     * @param string $moduleName The module name.
     * @param string $dependency The name of the dependency.
     */
    public function removeDependency($moduleName, $dependency)
    {
        unset($this->dependencies[$moduleName][$dependency]);
    }

    /**
     * Returns whether a module directly depends on another module.
     *
     * @param string $moduleName The module name.
     * @param string $dependency The name of the dependency.
     * @param bool   $recursive  Whether to take recursive dependencies into
     *                           account.
     *
     * @return bool Whether an edge exists from the origin to the target module.
     */
    public function hasDependency($moduleName, $dependency, $recursive = true)
    {
        if ($recursive) {
            return $this->hasPath($moduleName, $dependency);
        }

        return isset($this->dependencies[$moduleName][$dependency]);
    }

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

        // adjacent node
        if (isset($this->dependencies[$moduleName][$dependency])) {
            return true;
        }

        // DFS
        foreach ($this->dependencies[$moduleName] as $predecessor => $_) {
            if ($this->hasPath($predecessor, $dependency)) {
                return true;
            }
        }

        return false;
    }

    /**
     * Returns the path from a module name to a dependency.
     *
     * @param string $moduleName The module name.
     * @param string $dependency The name of the dependency.
     *
     * @return null|string[] The sorted module names on the path or `null` if no

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

        return null;
    }

    /**
     * Finds a path between modules using Depth-First Search.
     *
     * @param string $moduleName  The end module name.
     * @param string $dependency  The start module name.
     * @param array  $reversePath The path in reverse order.
     *
     * @return bool Whether a path was found.
     */
    private function getPathDFS($moduleName, $dependency, &$reversePath = array())
    {
        // does not exist in the graph
        if (!isset($this->dependencies[$moduleName])) {
            return false;
        }

        $reversePath[] = $moduleName;

        // adjacent node
        if (isset($this->dependencies[$moduleName][$dependency])) {
            $reversePath[] = $dependency;

            return true;
        }

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

        return false;
    }

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

        // Before adding the module itself to the path, add all predecessors.
        // Do so recursively, then we make sure that each module is visited
        // in the path before any of its successors.
        foreach ($this->dependencies[$currentName] as $predecessor => $_) {
            // The module was already processed. Either the module 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->sortModulesDFS($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\Module\ModuleList;
15		use RuntimeException;
16
17		/**
18		* A directed, acyclic graph of module names.
19		*
20		* Modules can be added with {@link addModuleName()}. Edges between these modules
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 DependencyGraph();
26		* $graph->addModuleName('acme/core');
27		* $graph->addModuleName('acme/blog');
28		* $graph->addModuleName('acme/blog-extension1');
29		* $graph->addModuleName('acme/blog-extension2');
30		* $graph->addDependency('acme/blog', 'acme/core');
31		* $graph->addDependency('acme/blog-extension1', 'acme/blog');
32		* $graph->addDependency('acme/blog-extension2', 'acme/blog');
33		* $graph->addDependency('acme/blog-extension2', 'acme/blog-extension1');
34		* ```
35		*
36		* You can use {@link getPath()} and {@link hasPath()} to check whether a path
37		* exists from one module to the other:
38		*
39		* ```php
40		* // ...
41		*
42		* $graph->hasPath('acme/blog-extension1', 'acme/blog');
43		* // => true
44		*
45		* $graph->hasPath('acme/blog-extension2', 'acme/blog-extension1');
46		* // => false
47		*
48		* $graph->getPath('acme/blog-extension2', 'acme/core');
49		* // => array('acme/core', 'acme/blog', 'acme/blog-extension2')
50		* ```
51		*
52		* With {@link getSortedModuleNames()}, you can sort the modules such that the
53		* dependencies defined via the edges are respected:
54		*
55		* ```php
56		* // ...
57		*
58		* $graph->getSortedModuleNames();
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 DependencyGraph
67		{
68		/**
69		* Stores the names of all modules (vertices) as keys.
70		*
71		* @var array
72		*/
73		private $moduleNames = array();
74
75		/**
76		* Stores the edges in the keys of a multi-dimensional array.
77		*
78		* The first dimension stores the module names, the second dimension the
79		* names of the dependencies.
80		*
81		* @var array
82		*/
83		private $dependencies = array();
84
85		/**
86		* Creates an override graph for the given modules.
87		*
88		* @param ModuleList $modules The modules to load.
89		*
90		* @return static The created override graph.
91		*/
92	93	public static function forModules(ModuleList $modules)
93		{
94	93	$graph = new static($modules->getModuleNames());
95
96	93	foreach ($modules as $module) {
97	93	if (null === $module->getModuleFile()) {
98	2	continue;
99		}
100
101	93	foreach ($module->getModuleFile()->getDependencies() as $dependency) {
102	35	if ($graph->hasModuleName($dependency)) {
103	93	$graph->addDependency($module->getName(), $dependency);
104		}
105		}
106		}
107
108		// Do we have a root module?
109	93	if (null === $modules->getRootModule()) {
110	20	return $graph;
111		}
112
113		// Make sure we have numeric, ascending keys here
114	73	$moduleOrder = array_values($modules->getRootModule()->getModuleFile()->getModuleOrder());
115
116		// Each module overrides the previous one in the list
117	73	for ($i = 1, $l = count($moduleOrder); $i < $l; ++$i) {
118	1	$dependency = $moduleOrder[$i - 1];
119	1	$moduleName = $moduleOrder[$i];
120
121	1	if ($graph->hasModuleName($dependency)) {
122	1	$graph->addDependency($moduleName, $dependency);
123		}
124		}
125
126	73	return $graph;
127		}
128
129		/**
130		* Creates a new graph.
131		*
132		* @param string[] $moduleNames The module names stored in the nodes of
133		* the graph.
134		*/
135	132	public function __construct(array $moduleNames = array())
136		{
137	132	$this->addModuleNames($moduleNames);
138	132	}
139
140		/**
141		* Adds a module name to the graph.
142		*
143		* @param string $moduleName The module name.
144		*
145		* @throws RuntimeException If the module name already exists.
146		*/
147	131	public function addModuleName($moduleName)
148		{
149	131	if (isset($this->moduleNames[$moduleName])) {
150	1	throw new RuntimeException(sprintf(
151	1	'The module "%s" was added to the graph twice.',
152		$moduleName
153		));
154		}
155
156	131	$this->moduleNames[$moduleName] = true;
157	131	$this->dependencies[$moduleName] = array();
158	131	}
159
160		/**
161		* Adds a list of module names to the graph.
162		*
163		* @param string[] $moduleNames The module names.
164		*
165		* @throws RuntimeException If a module name already exists.
166		*/
167	132	public function addModuleNames(array $moduleNames)
168		{
169	132	foreach ($moduleNames as $moduleName) {
170	105	$this->addModuleName($moduleName);
171		}
172	132	}
173
174		/**
175		* Returns whether a module name exists in the graph.
176		*
177		* @param string $moduleName The module name.
178		*
179		* @return bool Whether the module name exists.
180		*/
181	40	public function hasModuleName($moduleName)
182		{
183	40	return isset($this->moduleNames[$moduleName]);
184		}
185
186		/**
187		* Returns all module names in the graph.
188		*
189		* @return array All module names in the graph.
190		*/
191		public function getModuleNames()
192		{
193		return $this->moduleNames;
194		}
195
196		/**
197		* Returns the sorted module names.
198		*
199		* The names are sorted such that if a module m1 depends on a module m2,
200		* then m2 comes before m1 in the sorted set.
201		*
202		* If module names are passed, only those module names are sorted. Otherwise
203		* all module names are sorted.
204		*
205		* @param string[] $namesToSort The module names which should be sorted.
206		*
207		* @return string[] The sorted module names.
208		*
209		* @throws RuntimeException If any of the passed module names does not
210		* exist in the graph.
211		*/
212	83	public function getSortedModuleNames(array $namesToSort = array())
213		{
214	83	if (count($namesToSort) > 0) {
215	54	$namesToSort = array_flip($namesToSort);
216
217	54	foreach ($namesToSort as $module => $_) {
218	54	if (!isset($this->moduleNames[$module])) {
219	1	throw new RuntimeException(sprintf(
220	54	'The module "%s" does not exist in the graph.',
221		$module
222		));
223		}
224		}
225		} else {
226	29	$namesToSort = $this->moduleNames;
227		}
228
229	82	$sorted = array();
230
231		// Do a topologic sort
232		// Start with any module and process until no more are left
233	82	while (false !== reset($namesToSort)) {
234	82	$this->sortModulesDFS(key($namesToSort), $namesToSort, $sorted);
235		}
236
237	82	return $sorted;
238		}
239
240		/**
241		* Adds a dependency from one to another module.
242		*
243		* @param string $moduleName The module name.
244		* @param string $dependency The name of the dependency.
245		*/
246	67	public function addDependency($moduleName, $dependency)
247		{
248	67	if (!isset($this->moduleNames[$dependency])) {
249	1	throw new RuntimeException(sprintf(
250	1	'The module "%s" does not exist in the graph.',
251		$dependency
252		));
253		}
254
255	66	if (!isset($this->moduleNames[$moduleName])) {
256	1	throw new RuntimeException(sprintf(
257	1	'The module "%s" does not exist in the graph.',
258		$moduleName
259		));
260		}
261
262	65	if (null !== ($path = $this->getPath($dependency, $moduleName))) {
263	1	$last = array_pop($path);
264
265	1	throw new CyclicDependencyException(sprintf(
266		'A cyclic dependency was discovered between the modules "%s" '.
267		'and "%s". Please check the "override" keys defined in these '.
268	1	'modules.',
269	1	implode('", "', $path),
270		$last
271		));
272		}
273
274	65	$this->dependencies[$moduleName][$dependency] = true;
275	65	}
276
277		/**
278		* Removes a dependency from one to another module.
279		*
280		* @param string $moduleName The module name.
281		* @param string $dependency The name of the dependency.
282		*/
283	2	public function removeDependency($moduleName, $dependency)
284		{
285	2	unset($this->dependencies[$moduleName][$dependency]);
286	2	}
287
288		/**
289		* Returns whether a module directly depends on another module.
290		*
291		* @param string $moduleName The module name.
292		* @param string $dependency The name of the dependency.
293		* @param bool $recursive Whether to take recursive dependencies into
294		* account.
295		*
296		* @return bool Whether an edge exists from the origin to the target module.
297		*/
298	40	public function hasDependency($moduleName, $dependency, $recursive = true)
299		{
300	40	if ($recursive) {
301	9	return $this->hasPath($moduleName, $dependency);
302		}
303
304	39	return isset($this->dependencies[$moduleName][$dependency]);
305		}
306
307		/**
308		* Returns whether a path exists from a module to a dependency.
309		*
310		* @param string $moduleName The module name.
311		* @param string $dependency The name of the dependency.
312		*
313		* @return bool Whether a path exists from the origin to the target module.
314		*/
315	18	public function hasPath($moduleName, $dependency)
316		{
317		// does not exist in the graph
318	18	if (!isset($this->dependencies[$moduleName])) {
319	2	return false;
320		}
321
322		// adjacent node
323	17	if (isset($this->dependencies[$moduleName][$dependency])) {
324	4	return true;
325		}
326
327		// DFS
328	15	foreach ($this->dependencies[$moduleName] as $predecessor => $_) {
329	4	if ($this->hasPath($predecessor, $dependency)) {
330	4	return true;
331		}
332		}
333
334	14	return false;
335		}
336
337		/**
338		* Returns the path from a module name to a dependency.
339		*
340		* @param string $moduleName The module name.
341		* @param string $dependency The name of the dependency.
342		*
343		* @return null\|string[] The sorted module names on the path or `null` if no
		0 ignored issues – show Documentation introduced 2016-02-01 16:48 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...
344		* path was found.
345		*/
346	65	public function getPath($moduleName, $dependency)
347		{
348	65	if ($this->getPathDFS($moduleName, $dependency, $reversePath)) {
349	3	return array_reverse($reversePath);
350		}
351
352	65	return null;
353		}
354
355		/**
356		* Finds a path between modules using Depth-First Search.
357		*
358		* @param string $moduleName The end module name.
359		* @param string $dependency The start module name.
360		* @param array $reversePath The path in reverse order.
361		*
362		* @return bool Whether a path was found.
363		*/
364	65	private function getPathDFS($moduleName, $dependency, &$reversePath = array())
365		{
366		// does not exist in the graph
367	65	if (!isset($this->dependencies[$moduleName])) {
368	1	return false;
369		}
370
371	65	$reversePath[] = $moduleName;
372
373		// adjacent node
374	65	if (isset($this->dependencies[$moduleName][$dependency])) {
375	3	$reversePath[] = $dependency;
376
377	3	return true;
378		}
379
380		// DFS
381	65	foreach ($this->dependencies[$moduleName] as $predecessor => $_) {
382	45	if ($this->getPathDFS($predecessor, $dependency, $reversePath)) {
383	45	return true;
384		}
385		}
386
387	65	return false;
388		}
389
390		/**
391		* Topologically sorts the given module name into the output array.
392		*
393		* The resulting array is sorted such that all predecessors of the module
394		* come before the module (and their predecessors before them, and so on).
395		*
396		* @param string $currentName The current module name to sort.
397		* @param array $namesToSort The module names yet to be sorted.
398		* @param array $output The output array.
399		*/
400	82	private function sortModulesDFS($currentName, array &$namesToSort, array &$output)
401		{
402	82	unset($namesToSort[$currentName]);
403
404		// Before adding the module itself to the path, add all predecessors.
405		// Do so recursively, then we make sure that each module is visited
406		// in the path before any of its successors.
407	82	foreach ($this->dependencies[$currentName] as $predecessor => $_) {
408		// The module was already processed. Either the module is on the
409		// path already, then we're good. Otherwise, we have a cycle.
410		// However, addEdge() guarantees that the graph is cycle-free.
411	44	if (isset($namesToSort[$predecessor])) {
412	44	$this->sortModulesDFS($predecessor, $namesToSort, $output);
413		}
414		}
415
416	82	$output[] = $currentName;
417	82	}
418		}
419

puli / manager

Push — master ( e3306a...3ebd86 )

DependencyGraph::getModuleNames() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like