1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
<?php
/**
* Copyright © Magento, Inc. All rights reserved.
* See COPYING.txt for license details.
*/
namespace Magento\Setup\Module\Dependency;
use Magento\Framework\Data\Graph;
/**
* Build circular dependencies by modules map
*/
class Circular
{
/**
* Map where the key is the vertex and the value are the adjacent vertices(dependencies) of this vertex
*
* @var array
*/
protected $dependencies = [];
/**
* Modules circular dependencies map
*
* @var array
*/
protected $circularDependencies = [];
/**
* Graph object
*
* @var \Magento\Framework\Data\Graph
*/
protected $graph;
/**
* Build modules dependencies
*
* @param array $dependencies Key is the vertex and the value are the adjacent vertices(dependencies) of this vertex
* @return array
*/
public function buildCircularDependencies($dependencies)
{
$this->init($dependencies);
foreach (array_keys($this->dependencies) as $vertex) {
$this->expandDependencies($vertex);
}
$circulars = $this->graph->findCycle(null, false);
foreach ($circulars as $circular) {
array_shift($circular);
$this->buildCircular($circular);
}
return $this->divideByModules($this->circularDependencies);
}
/**
* Init data before building
*
* @param array $dependencies
* @return void
*/
protected function init($dependencies)
{
$this->dependencies = $dependencies;
$this->circularDependencies = [];
$this->graph = new Graph(array_keys($this->dependencies), []);
}
/**
* Expand modules dependencies from chain
*
* @param string $vertex
* @param array $path nesting path
* @return void
*/
protected function expandDependencies($vertex, $path = [])
{
if (!$this->dependencies[$vertex]) {
return;
}
$path[] = $vertex;
foreach ($this->dependencies[$vertex] as $dependency) {
if (!isset($this->dependencies[$dependency])) {
// dependency vertex is not described in basic definition
continue;
}
$relations = $this->graph->getRelations();
if (isset($relations[$vertex][$dependency])) {
continue;
}
$this->graph->addRelation($vertex, $dependency);
$searchResult = array_search($dependency, $path);
if (false !== $searchResult) {
$this->buildCircular(array_slice($path, $searchResult));
break;
} else {
$this->expandDependencies($dependency, $path);
}
}
}
/**
* Build all circular dependencies based on chain
*
* @param array $modules
* @return void
*/
protected function buildCircular($modules)
{
$path = '/' . implode('/', $modules);
if (isset($this->circularDependencies[$path])) {
return;
}
$this->circularDependencies[$path] = $modules;
$modules[] = array_shift($modules);
$this->buildCircular($modules);
}
/**
* Divide dependencies by modules
*
* @param array $circularDependencies
* @return array
*/
protected function divideByModules($circularDependencies)
{
$dependenciesByModule = [];
foreach ($circularDependencies as $circularDependency) {
$module = $circularDependency[0];
$circularDependency[] = $module;
$dependenciesByModule[$module][] = $circularDependency;
}
return $dependenciesByModule;
}
}