[TASK] Add extension precedence
[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 use TYPO3\CMS\Core\Core\Bootstrap;
17
18 /**
19 * This class takes care about dependencies between packages.
20 * It provides functionality to resolve dependencies and to determine
21 * the crucial loading order of the packages.
22 *
23 * @author Markus Klein <klein.t3@mfc-linz.at>
24 */
25 class DependencyResolver {
26
27 /**
28 * Folder with framework extensions
29 */
30 const SYSEXT_FOLDER = 'typo3/sysext';
31
32 /**
33 * @param array $packageStatesConfiguration
34 * @return array Returns the packageStatesConfiguration sorted by dependencies
35 * @throws \UnexpectedValueException
36 */
37 public function sortPackageStatesConfigurationByDependency(array $packageStatesConfiguration) {
38 // We just want to consider active packages
39 $activePackageStatesConfiguration = $this->removeInactivePackagesFromPackageStateConfiguration($packageStatesConfiguration);
40 $inactivePackageStatesConfiguration = array_diff_key($packageStatesConfiguration, $activePackageStatesConfiguration);
41
42 /*
43 * Adjacency matrix for the dependency graph (DAG)
44 *
45 * Example structure is:
46 * A => (A => FALSE, B => TRUE, C => FALSE)
47 * B => (A => FALSE, B => FALSE, C => FALSE)
48 * C => (A => TRUE, B => FALSE, C => FALSE)
49 *
50 * A depends on B, C depends on A, B is independent
51 */
52 $dependencyGraph = $this->buildDependencyGraph($activePackageStatesConfiguration);
53
54 // Filter extensions with no incoming edge
55 $rootPackageKeys = array();
56 foreach ($dependencyGraph as $packageKey => $_) {
57 if (!$this->getIncomingEdgeCount($dependencyGraph, $packageKey)) {
58 $rootPackageKeys[] = $packageKey;
59 }
60 }
61
62 // This will contain our final result
63 $sortedPackageKeys = array();
64
65 // Walk through the graph
66 while (count($rootPackageKeys)) {
67 $currentPackageKey = array_shift($rootPackageKeys);
68 array_push($sortedPackageKeys, $currentPackageKey);
69
70 foreach (array_filter($dependencyGraph[$currentPackageKey]) 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_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 ($dependencyGraph as $packageKey => $_) {
204 if (!$this->getIncomingEdgeCount($dependencyGraph, $packageKey)) {
205 $rootPackageKeys[] = $packageKey;
206 }
207 }
208 $frameworkPackageKeys = $this->findFrameworkPackages($packageStateConfiguration);
209 $extensionPackageKeys = array_diff(array_keys($packageStateConfiguration), $frameworkPackageKeys);
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->findFrameworkPackages($packageStateConfiguration);
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 * @param array $packageStateConfiguration
246 * @return array
247 * @throws \TYPO3\CMS\Core\Exception
248 */
249 protected function findFrameworkPackages(array $packageStateConfiguration) {
250 $frameworkPackageKeys = array();
251 /** @var PackageManager $packageManager */
252 $packageManager = Bootstrap::getInstance()->getEarlyInstance(\TYPO3\Flow\Package\PackageManager::class);
253 foreach ($packageStateConfiguration as $packageKey => $packageConfiguration) {
254 /** @var Package $package */
255 $package = $packageManager->getPackage($packageKey);
256 if ($package->isPartOfFactoryDefault() || $package->isPartOfMinimalUsableSystem() || strpos($packageConfiguration['packagePath'], self::SYSEXT_FOLDER) === 0) {
257 $frameworkPackageKeys[] = $packageKey;
258 }
259 }
260
261 return $frameworkPackageKeys;
262 }
263
264 /**
265 * Get the number of incoming edges in the dependency graph
266 * for given package key.
267 *
268 * @param array $dependencyGraph
269 * @param string $packageKey
270 * @return int
271 */
272 protected function getIncomingEdgeCount(array $dependencyGraph, $packageKey) {
273 $incomingEdgeCount = 0;
274 foreach ($dependencyGraph as $dependencies) {
275 if ($dependencies[$packageKey]) {
276 $incomingEdgeCount++;
277 }
278 }
279 return $incomingEdgeCount;
280 }
281
282 }