f98b42a07284ebbe85027d7054840df229c457e0
[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 $dependencyGraph = array_fill_keys($packageKeys, array_fill_keys($packageKeys, FALSE));
132 foreach ($packageKeys as $packageKey) {
133 if (!isset($packageStatesConfiguration[$packageKey]['dependencies'])) {
134 continue;
135 }
136 $dependentPackageKeys = $packageStatesConfiguration[$packageKey]['dependencies'];
137 foreach ($dependentPackageKeys as $dependentPackageKey) {
138 if (!in_array($dependentPackageKey, $packageKeys)) {
139 throw new \UnexpectedValueException(
140 'The package "' . $packageKey .'" depends on "'
141 . $dependentPackageKey . '" which is not present in the system.',
142 1382276561);
143 }
144 $dependencyGraph[$packageKey][$dependentPackageKey] = TRUE;
145 }
146 }
147 foreach ($packageKeys as $packageKey) {
148 if (!isset($packageStatesConfiguration[$packageKey]['suggestions'])) {
149 continue;
150 }
151 $suggestedPackageKeys = $packageStatesConfiguration[$packageKey]['suggestions'];
152 foreach ($suggestedPackageKeys as $suggestedPackageKey) {
153 if (!in_array($suggestedPackageKey, $packageKeys)) {
154 continue;
155 }
156 // Check if there's no dependency of the suggestion to the package
157 // Dependencies take precedence over suggestions
158 $dependencies = $this->findPathInGraph($dependencyGraph, $suggestedPackageKey, $packageKey);
159 if (empty($dependencies)) {
160 $dependencyGraph[$packageKey][$suggestedPackageKey] = TRUE;
161 }
162 }
163 }
164 return $dependencyGraph;
165 }
166
167 /**
168 * Find any path in the graph from given start node to destination node
169 *
170 * @param array $graph Directed graph
171 * @param string $from Start node
172 * @param string $to Destination node
173 * @return array Nodes of the found path; empty if no path is found
174 */
175 protected function findPathInGraph(array $graph, $from, $to) {
176 foreach (array_keys(array_filter($graph[$from])) as $node) {
177 if ($node === $to) {
178 return array($from, $to);
179 } else {
180 $subPath = $this->findPathInGraph($graph, $node, $to);
181 if (!empty($subPath)) {
182 array_unshift($subPath, $from);
183 return $subPath;
184 }
185 }
186 }
187 return array();
188 }
189
190 /**
191 * Adds all root packages of current dependency graph as dependency
192 * to all extensions.
193 * This ensures that the framework extensions (aka sysext) are
194 * always loaded first, before any other external extension.
195 *
196 * @param array $packageStateConfiguration
197 * @param array $dependencyGraph
198 * @return array
199 */
200 protected function addDependencyToFrameworkToAllExtensions(array $packageStateConfiguration, array $dependencyGraph) {
201 $rootPackageKeys = array();
202 foreach (array_keys($dependencyGraph) as $packageKey) {
203 if (!$this->getIncomingEdgeCount($dependencyGraph, $packageKey)) {
204 $rootPackageKeys[] = $packageKey;
205 }
206 }
207 $extensionPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, '', array(self::SYSEXT_FOLDER));
208 $frameworkPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, self::SYSEXT_FOLDER);
209 foreach ($extensionPackageKeys as $packageKey) {
210 // Remove framework packages from list
211 $packageKeysWithoutFramework = array_diff(
212 $packageStateConfiguration[$packageKey]['dependencies'],
213 $frameworkPackageKeys
214 );
215 // The order of the array_merge is crucial here,
216 // we want the framework first
217 $packageStateConfiguration[$packageKey]['dependencies'] = array_merge(
218 $rootPackageKeys, $packageKeysWithoutFramework
219 );
220 }
221 return $packageStateConfiguration;
222 }
223
224 /**
225 * Builds the dependency graph for all packages
226 *
227 * This method also introduces dependencies among the dependencies
228 * to ensure the loading order is exactly as specified in the list.
229 *
230 * @param array $packageStateConfiguration
231 * @return array
232 */
233 protected function buildDependencyGraph(array $packageStateConfiguration) {
234 $frameworkPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, self::SYSEXT_FOLDER);
235 $dependencyGraph = $this->buildDependencyGraphForPackages($packageStateConfiguration, $frameworkPackageKeys);
236 $packageStateConfiguration = $this->addDependencyToFrameworkToAllExtensions($packageStateConfiguration, $dependencyGraph);
237
238 $packageKeys = array_keys($packageStateConfiguration);
239 $dependencyGraph = $this->buildDependencyGraphForPackages($packageStateConfiguration, $packageKeys);
240 return $dependencyGraph;
241 }
242
243
244
245 /**
246 * Get the number of incoming edges in the dependency graph
247 * for given package key.
248 *
249 * @param array $dependencyGraph
250 * @param string $packageKey
251 * @return integer
252 */
253 protected function getIncomingEdgeCount(array $dependencyGraph, $packageKey) {
254 $incomingEdgeCount = 0;
255 foreach ($dependencyGraph as $dependencies) {
256 if ($dependencies[$packageKey]) {
257 $incomingEdgeCount++;
258 }
259 }
260 return $incomingEdgeCount;
261 }
262
263 /**
264 * Get packages of specific type
265 *
266 * @param array $packageStateConfiguration
267 * @param string $basePath Base path of package. Empty string for all types
268 * @param array $excludedPaths Array of package base paths to exclude
269 * @return array List of packages
270 */
271 protected function getPackageKeysInBasePath(array $packageStateConfiguration, $basePath, array $excludedPaths = array()) {
272 $packageKeys = array();
273 foreach ($packageStateConfiguration as $packageKey => $package) {
274 if (($basePath === '' || strpos($package['packagePath'], $basePath) === 0)) {
275 $isExcluded = FALSE;
276 foreach ($excludedPaths as $excludedPath) {
277 if (strpos($package['packagePath'], $excludedPath) === 0) {
278 $isExcluded = TRUE;
279 break;
280 }
281 }
282 if (!$isExcluded) {
283 $packageKeys[] = $packageKey;
284 }
285 }
286 }
287 return $packageKeys;
288 }
289
290 }