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