OverrideGraph::forModules() - Code Metrics - Inspection of "Merge pull request #50 from webmozart/rename-packa..." - puli/manager - Measure and Improve Code Quality continuously with Scrutinizer

Failed Conditions

Push — master ( d49c03...6343d0 )

by Bernhard

created 2016-01-28 11:08 UTC

OverrideGraph::forModules() C

↳ Parent: OverrideGraph

Complexity

Conditions	8
Paths	12

Size

Total Lines	36
Code Lines	17

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	17
CRAP Score	8

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
c	1
b	0
f	0
dl	0
loc	36
ccs	17
cts	17
cp	1
rs	5.3846
cc	8
eloc	17
nc	12
nop	1
crap	8

<?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\ModuleCollection;
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 OverrideGraph();
 * $graph->addModuleName('acme/core');
 * $graph->addModuleName('acme/blog');
 * $graph->addModuleName('acme/blog-extension1');
 * $graph->addModuleName('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 module 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 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 OverrideGraph
{
    /**
     * 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 targets, the second dimension the origins
     * of the edges.
     *
     * @var array
     */
    private $edges = array();

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

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

            foreach ($module->getModuleFile()->getOverriddenModules() as $overriddenModule) {
                if ($graph->hasModuleName($overriddenModule)) {
                    $graph->addEdge($overriddenModule, $module->getName());
                }
            }
        }

        // 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()->getOverrideOrder());

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

            if ($graph->hasModuleName($overriddenModule)) {
                $graph->addEdge($overriddenModule, $overridingModule);
            }
        }

        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->edges[$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]);
    }

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

        if (!isset($this->moduleNames[$to])) {
            throw new RuntimeException(sprintf(
                'The module "%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 modules "%s" '.
                'and "%s". Please check the "override" keys defined in these '.
                'modules.',
                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 modules.
     *
     * @param string $from The start module name.
     * @param string $to   The end module name.
     *
     * @return bool Whether an edge exists from the origin to the target module.
     */
    public function hasEdge($from, $to)
    {
        return isset($this->edges[$to][$from]);
    }

    /**
     * Returns whether a path exists from one to another module.
     *
     * @param string $from The start module name.
     * @param string $to   The end module name.
     *
     * @return bool Whether a path exists from the origin to the target module.
     */
    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 module.
     *
     * @param string $from The start module name.
     * @param string $to   The end module name.
     *
     * @return string[]|null The path of module 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 module names in the graph.
     *
     * @return array All module names in the graph.
     */
    public function getModuleNames()
    {
        return $this->moduleNames;
    }

    /**
     * Sorts module names according to the defined edges.
     *
     * The names are sorted such that if two modules p1 and p2 have an edge
     * (p1, p2) in the graph, then p1 comes before p2 in the sorted set.
     *
     * If no module names are passed, all 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;
    }

    /**
     * Finds a path between modules using Depth-First Search.
     *
     * @param string $from        The start module name.
     * @param string $to          The end module 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 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->edges[$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\ModuleCollection;
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 OverrideGraph();
26		* $graph->addModuleName('acme/core');
27		* $graph->addModuleName('acme/blog');
28		* $graph->addModuleName('acme/blog-extension1');
29		* $graph->addModuleName('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 module 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 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 OverrideGraph
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 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 modules.
87		*
88		* @param ModuleCollection $modules The modules to load.
89		*
90		* @return static The created override graph.
91		*/
92	93	public static function forModules(ModuleCollection $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()->getOverriddenModules() as $overriddenModule) {
102	35	if ($graph->hasModuleName($overriddenModule)) {
103	93	$graph->addEdge($overriddenModule, $module->getName());
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()->getOverrideOrder());
115
116		// Each module overrides the previous one in the list
117	73	for ($i = 1, $l = count($moduleOrder); $i < $l; ++$i) {
118	1	$overriddenModule = $moduleOrder[$i - 1];
119	1	$overridingModule = $moduleOrder[$i];
120
121	1	if ($graph->hasModuleName($overriddenModule)) {
122	1	$graph->addEdge($overriddenModule, $overridingModule);
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->edges[$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		* Adds a directed edge from one to another module.
188		*
189		* @param string $from The start module name.
190		* @param string $to The end module name.
191		*
192		* @throws RuntimeException If any of the modules does not exist in the
193		* graph. Each module 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->moduleNames[$from])) {
199	1	throw new RuntimeException(sprintf(
200	1	'The module "%s" does not exist in the graph.',
201		$from
202		));
203		}
204
205	66	if (!isset($this->moduleNames[$to])) {
206	1	throw new RuntimeException(sprintf(
207	1	'The module "%s" does not exist in the graph.',
208		$to
209		));
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 modules "%s" '.
217		'and "%s". Please check the "override" keys defined in these '.
218	1	'modules.',
219	1	implode('", "', $path),
220		$last
221		));
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 modules.
234		*
235		* @param string $from The start module name.
236		* @param string $to The end module name.
237		*
238		* @return bool Whether an edge exists from the origin to the target module.
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 module.
247		*
248		* @param string $from The start module name.
249		* @param string $to The end module name.
250		*
251		* @return bool Whether a path exists from the origin to the target module.
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	2	return true;
269		}
270		}
271
272	6	return false;
273		}
274
275		/**
276		* Returns the path from one to another module.
277		*
278		* @param string $from The start module name.
279		* @param string $to The end module name.
280		*
281		* @return string[]\|null The path of module 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 module names in the graph.
295		*
296		* @return array All module names in the graph.
297		*/
298		public function getModuleNames()
299		{
300		return $this->moduleNames;
301		}
302
303		/**
304		* Sorts module names according to the defined edges.
305		*
306		* The names are sorted such that if two modules 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 module names are passed, all names are sorted.
310		*
311		* @param string[] $namesToSort The module names which should be sorted.
312		*
313		* @return string[] The sorted module names.
314		*
315		* @throws RuntimeException If any of the passed module names does not
316		* exist in the graph.
317		*/
318	83	public function getSortedModuleNames(array $namesToSort = array())
319		{
320	83	if (count($namesToSort) > 0) {
321	54	$namesToSort = array_flip($namesToSort);
322
323	54	foreach ($namesToSort as $module => $_) {
324	54	if (!isset($this->moduleNames[$module])) {
325	1	throw new RuntimeException(sprintf(
326	54	'The module "%s" does not exist in the graph.',
327		$module
328		));
329		}
330		}
331		} else {
332	29	$namesToSort = $this->moduleNames;
333		}
334
335	82	$sorted = array();
336
337		// Do a topologic sort
338		// Start with any module and process until no more are left
339	82	while (false !== reset($namesToSort)) {
340	82	$this->sortModulesDFS(key($namesToSort), $namesToSort, $sorted);
341		}
342
343	82	return $sorted;
344		}
345
346		/**
347		* Finds a path between modules using Depth-First Search.
348		*
349		* @param string $from The start module name.
350		* @param string $to The end module 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())
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	44	return true;
375		}
376		}
377
378	65	return false;
379		}
380
381		/**
382		* Topologically sorts the given module name into the output array.
383		*
384		* The resulting array is sorted such that all predecessors of the module
385		* come before the module (and their predecessors before them, and so on).
386		*
387		* @param string $currentName The current module name to sort.
388		* @param array $namesToSort The module names yet to be sorted.
389		* @param array $output The output array.
390		*/
391	82	private function sortModulesDFS($currentName, array &$namesToSort, array &$output)
392		{
393	82	unset($namesToSort[$currentName]);
394
395		// Before adding the module itself to the path, add all predecessors.
396		// Do so recursively, then we make sure that each module is visited
397		// in the path before any of its successors.
398	82	foreach ($this->edges[$currentName] as $predecessor => $_) {
399		// The module was already processed. Either the module 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	44	$this->sortModulesDFS($predecessor, $namesToSort, $output);
404		}
405		}
406
407	82	$output[] = $currentName;
408	82	}
409		}
410

puli / manager

Push — master ( d49c03...6343d0 )

OverrideGraph::forModules() C

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like