[TASK] Keep the changes to PackageStates.php low
[Packages/TYPO3.CMS.git] / typo3 / sysext / core / Classes / Package / DependencyResolver.php
1 <?php
2 namespace TYPO3\CMS\Core\Package;
3
4 /**
5 * This file is part of the TYPO3 CMS project.
6 *
7 * It is free software; you can redistribute it and/or modify it under
8 * the terms of the GNU General Public License, either version 2
9 * of the License, or any later version.
10 *
11 * For the full copyright and license information, please read the
12 * LICENSE.txt file that was distributed with this source code.
13 *
14 * The TYPO3 project - inspiring people to share!
15 */
16
17 /**
18 * This class takes care about dependencies between packages.
19 * It provides functionality to resolve dependencies and to determine
20 * the crucial loading order of the packages.
21 *
22 * @author Markus Klein <klein.t3@mfc-linz.at>
23 */
24 class DependencyResolver {
25
26 /**
27 * Folder with framework extensions
28 */
29 const SYSEXT_FOLDER = 'typo3/sysext';
30
31 /**
32 * @param array $packageStatesConfiguration
33 * @return array Returns the packageStatesConfiguration sorted by dependencies
34 * @throws \UnexpectedValueException
35 */
36 public function sortPackageStatesConfigurationByDependency(array $packageStatesConfiguration) {
37 // We just want to consider active packages
38 $activePackageStatesConfiguration = $this->removeInactivePackagesFromPackageStateConfiguration($packageStatesConfiguration);
39 $inactivePackageStatesConfiguration = array_diff_key($packageStatesConfiguration, $activePackageStatesConfiguration);
40
41 /*
42 * Adjacency matrix for the dependency graph (DAG)
43 *
44 * Example structure is:
45 * A => (A => FALSE, B => TRUE, C => FALSE)
46 * B => (A => FALSE, B => FALSE, C => FALSE)
47 * C => (A => TRUE, B => FALSE, C => FALSE)
48 *
49 * A depends on B, C depends on A, B is independent
50 */
51 $dependencyGraph = $this->buildDependencyGraph($activePackageStatesConfiguration);
52
53 // Filter extensions with no incoming edge
54 $rootPackageKeys = array();
55 foreach (array_keys($dependencyGraph) as $packageKey) {
56 if (!$this->getIncomingEdgeCount($dependencyGraph, $packageKey)) {
57 $rootPackageKeys[] = $packageKey;
58 }
59 }
60
61 // This will contain our final result
62 $sortedPackageKeys = array();
63
64 // Walk through the graph
65 while (count($rootPackageKeys)) {
66 $currentPackageKey = array_shift($rootPackageKeys);
67 array_push($sortedPackageKeys, $currentPackageKey);
68
69 $dependingPackageKeys = array_keys(array_filter($dependencyGraph[$currentPackageKey]));
70 foreach ($dependingPackageKeys as $dependingPackageKey) {
71 // Remove the edge to this dependency
72 $dependencyGraph[$currentPackageKey][$dependingPackageKey] = FALSE;
73 if (!$this->getIncomingEdgeCount($dependencyGraph, $dependingPackageKey)) {
74 // We found a new root, lets add it
75 array_unshift($rootPackageKeys, $dependingPackageKey);
76 }
77 }
78 }
79
80 // Check for remaining edges in the graph
81 $cycles = array();
82 array_walk($dependencyGraph, function($dependencies, $packageKeyFrom) use(&$cycles) {
83 array_walk($dependencies, function($dependency, $packageKeyTo) use(&$cycles, $packageKeyFrom) {
84 if ($dependency) {
85 $cycles[] = $packageKeyFrom . '->' . $packageKeyTo;
86 }
87 });
88 });
89 if (count($cycles)) {
90 throw new \UnexpectedValueException('Your dependencies have cycles. That will not work out. Cycles found: ' . implode(', ', $cycles), 1381960493);
91 }
92
93 // We built now a list of dependencies
94 // Reverse the list to get the correct loading order
95 $sortedPackageKeys = array_reverse($sortedPackageKeys);
96
97 // Reorder the package states according to the loading order
98 $newPackageStatesConfiguration = array();
99 foreach ($sortedPackageKeys as $packageKey) {
100 $newPackageStatesConfiguration[$packageKey] = $packageStatesConfiguration[$packageKey];
101 }
102
103 // Append the inactive configurations again
104 $newPackageStatesConfiguration = array_merge($newPackageStatesConfiguration, $inactivePackageStatesConfiguration);
105
106 return $newPackageStatesConfiguration;
107 }
108
109 /**
110 * Returns only active package state configurations
111 *
112 * @param array $packageStatesConfiguration
113 * @return array
114 */
115 protected function removeInactivePackagesFromPackageStateConfiguration(array $packageStatesConfiguration) {
116 return array_filter($packageStatesConfiguration, function($packageState) {
117 return isset($packageState['state']) && $packageState['state'] === 'active';
118 });
119 }
120
121 /**
122 * Build the dependency graph for the given packages
123 *
124 * @param array $packageStatesConfiguration
125 * @param array $packageKeys
126 * @return array
127 * @throws \UnexpectedValueException
128 */
129 protected function buildDependencyGraphForPackages(array $packageStatesConfiguration, array $packageKeys) {
130 // Initialize the dependencies with FALSE
131 sort($packageKeys);
132 $dependencyGraph = array_fill_keys($packageKeys, array_fill_keys($packageKeys, FALSE));
133 foreach ($packageKeys as $packageKey) {
134 if (!isset($packageStatesConfiguration[$packageKey]['dependencies'])) {
135 continue;
136 }
137 $dependentPackageKeys = $packageStatesConfiguration[$packageKey]['dependencies'];
138 foreach ($dependentPackageKeys as $dependentPackageKey) {
139 if (!in_array($dependentPackageKey, $packageKeys)) {
140 throw new \UnexpectedValueException(
141 'The package "' . $packageKey .'" depends on "'
142 . $dependentPackageKey . '" which is not present in the system.',
143 1382276561);
144 }
145 $dependencyGraph[$packageKey][$dependentPackageKey] = TRUE;
146 }
147 }
148 foreach ($packageKeys as $packageKey) {
149 if (!isset($packageStatesConfiguration[$packageKey]['suggestions'])) {
150 continue;
151 }
152 $suggestedPackageKeys = $packageStatesConfiguration[$packageKey]['suggestions'];
153 foreach ($suggestedPackageKeys as $suggestedPackageKey) {
154 if (!in_array($suggestedPackageKey, $packageKeys)) {
155 continue;
156 }
157 // Check if there's no dependency of the suggestion to the package
158 // Dependencies take precedence over suggestions
159 $dependencies = $this->findPathInGraph($dependencyGraph, $suggestedPackageKey, $packageKey);
160 if (empty($dependencies)) {
161 $dependencyGraph[$packageKey][$suggestedPackageKey] = TRUE;
162 }
163 }
164 }
165 return $dependencyGraph;
166 }
167
168 /**
169 * Find any path in the graph from given start node to destination node
170 *
171 * @param array $graph Directed graph
172 * @param string $from Start node
173 * @param string $to Destination node
174 * @return array Nodes of the found path; empty if no path is found
175 */
176 protected function findPathInGraph(array $graph, $from, $to) {
177 foreach (array_keys(array_filter($graph[$from])) as $node) {
178 if ($node === $to) {
179 return array($from, $to);
180 } else {
181 $subPath = $this->findPathInGraph($graph, $node, $to);
182 if (!empty($subPath)) {
183 array_unshift($subPath, $from);
184 return $subPath;
185 }
186 }
187 }
188 return array();
189 }
190
191 /**
192 * Adds all root packages of current dependency graph as dependency
193 * to all extensions.
194 * This ensures that the framework extensions (aka sysext) are
195 * always loaded first, before any other external extension.
196 *
197 * @param array $packageStateConfiguration
198 * @param array $dependencyGraph
199 * @return array
200 */
201 protected function addDependencyToFrameworkToAllExtensions(array $packageStateConfiguration, array $dependencyGraph) {
202 $rootPackageKeys = array();
203 foreach (array_keys($dependencyGraph) as $packageKey) {
204 if (!$this->getIncomingEdgeCount($dependencyGraph, $packageKey)) {
205 $rootPackageKeys[] = $packageKey;
206 }
207 }
208 $extensionPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, '', array(self::SYSEXT_FOLDER));
209 $frameworkPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, self::SYSEXT_FOLDER);
210 foreach ($extensionPackageKeys as $packageKey) {
211 // Remove framework packages from list
212 $packageKeysWithoutFramework = array_diff(
213 $packageStateConfiguration[$packageKey]['dependencies'],
214 $frameworkPackageKeys
215 );
216 // The order of the array_merge is crucial here,
217 // we want the framework first
218 $packageStateConfiguration[$packageKey]['dependencies'] = array_merge(
219 $rootPackageKeys, $packageKeysWithoutFramework
220 );
221 }
222 return $packageStateConfiguration;
223 }
224
225 /**
226 * Builds the dependency graph for all packages
227 *
228 * This method also introduces dependencies among the dependencies
229 * to ensure the loading order is exactly as specified in the list.
230 *
231 * @param array $packageStateConfiguration
232 * @return array
233 */
234 protected function buildDependencyGraph(array $packageStateConfiguration) {
235 $frameworkPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, self::SYSEXT_FOLDER);
236 $dependencyGraph = $this->buildDependencyGraphForPackages($packageStateConfiguration, $frameworkPackageKeys);
237 $packageStateConfiguration = $this->addDependencyToFrameworkToAllExtensions($packageStateConfiguration, $dependencyGraph);
238
239 $packageKeys = array_keys($packageStateConfiguration);
240 $dependencyGraph = $this->buildDependencyGraphForPackages($packageStateConfiguration, $packageKeys);
241 return $dependencyGraph;
242 }
243
244
245
246 /**
247 * Get the number of incoming edges in the dependency graph
248 * for given package key.
249 *
250 * @param array $dependencyGraph
251 * @param string $packageKey
252 * @return integer
253 */
254 protected function getIncomingEdgeCount(array $dependencyGraph, $packageKey) {
255 $incomingEdgeCount = 0;
256 foreach ($dependencyGraph as $dependencies) {
257 if ($dependencies[$packageKey]) {
258 $incomingEdgeCount++;
259 }
260 }
261 return $incomingEdgeCount;
262 }
263
264 /**
265 * Get packages of specific type
266 *
267 * @param array $packageStateConfiguration
268 * @param string $basePath Base path of package. Empty string for all types
269 * @param array $excludedPaths Array of package base paths to exclude
270 * @return array List of packages
271 */
272 protected function getPackageKeysInBasePath(array $packageStateConfiguration, $basePath, array $excludedPaths = array()) {
273 $packageKeys = array();
274 foreach ($packageStateConfiguration as $packageKey => $package) {
275 if (($basePath === '' || strpos($package['packagePath'], $basePath) === 0)) {
276 $isExcluded = FALSE;
277 foreach ($excludedPaths as $excludedPath) {
278 if (strpos($package['packagePath'], $excludedPath) === 0) {
279 $isExcluded = TRUE;
280 break;
281 }
282 }
283 if (!$isExcluded) {
284 $packageKeys[] = $packageKey;
285 }
286 }
287 }
288 return $packageKeys;
289 }
290
291 }