2419e492fdfe519ff2750d861aadea7adf99af84
[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 $dependentPackageKeys = $packageStatesConfiguration[$packageKey]['dependencies'];
144 foreach ($dependentPackageKeys as $dependentPackageKey) {
145 if (!in_array($dependentPackageKey, $packageKeys)) {
146 throw new \UnexpectedValueException(
147 'The package "' . $packageKey .'" depends on "'
148 . $dependentPackageKey . '" which is not present in the system.',
149 1382276561);
150 }
151 $dependencyGraph[$packageKey][$dependentPackageKey] = TRUE;
152 }
153 }
154 return $dependencyGraph;
155 }
156
157 /**
158 * Adds all root packages of current dependency graph as dependency
159 * to all extensions.
160 * This ensures that the framework extensions (aka sysext) are
161 * always loaded first, before any other external extension.
162 *
163 * @param array $packageStateConfiguration
164 * @param array $dependencyGraph
165 * @return array
166 */
167 protected function addDependencyToFrameworkToAllExtensions(array $packageStateConfiguration, array $dependencyGraph) {
168 $rootPackageKeys = array();
169 foreach (array_keys($dependencyGraph) as $packageKey) {
170 if (!$this->getIncomingEdgeCount($dependencyGraph, $packageKey)) {
171 $rootPackageKeys[] = $packageKey;
172 }
173 }
174 $extensionPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, '', array(self::SYSEXT_FOLDER));
175 $frameworkPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, self::SYSEXT_FOLDER);
176 foreach ($extensionPackageKeys as $packageKey) {
177 // Remove framework packages from list
178 $packageKeysWithoutFramework = array_diff(
179 $packageStateConfiguration[$packageKey]['dependencies'],
180 $frameworkPackageKeys
181 );
182 // The order of the array_merge is crucial here,
183 // we want the framework first
184 $packageStateConfiguration[$packageKey]['dependencies'] = array_merge(
185 $rootPackageKeys, $packageKeysWithoutFramework
186 );
187 }
188 return $packageStateConfiguration;
189 }
190
191 /**
192 * Builds the dependency graph for all packages
193 *
194 * This method also introduces dependencies among the dependencies
195 * to ensure the loading order is exactly as specified in the list.
196 *
197 * @param array $packageStateConfiguration
198 * @return array
199 */
200 protected function buildDependencyGraph(array $packageStateConfiguration) {
201 $frameworkPackageKeys = $this->getPackageKeysInBasePath($packageStateConfiguration, self::SYSEXT_FOLDER);
202 $dependencyGraph = $this->buildDependencyGraphForPackages($packageStateConfiguration, $frameworkPackageKeys);
203 $packageStateConfiguration = $this->addDependencyToFrameworkToAllExtensions($packageStateConfiguration, $dependencyGraph);
204
205 $packageKeys = array_keys($packageStateConfiguration);
206 $dependencyGraph = $this->buildDependencyGraphForPackages($packageStateConfiguration, $packageKeys);
207 return $dependencyGraph;
208 }
209
210
211
212 /**
213 * Get the number of incoming edges in the dependency graph
214 * for given package key.
215 *
216 * @param array $dependencyGraph
217 * @param string $packageKey
218 * @return integer
219 */
220 protected function getIncomingEdgeCount(array $dependencyGraph, $packageKey) {
221 $incomingEdgeCount = 0;
222 foreach ($dependencyGraph as $dependencies) {
223 if ($dependencies[$packageKey]) {
224 $incomingEdgeCount++;
225 }
226 }
227 return $incomingEdgeCount;
228 }
229
230 /**
231 * Get packages of specific type
232 *
233 * @param array $packageStateConfiguration
234 * @param string $basePath Base path of package. Empty string for all types
235 * @param array $excludedPaths Array of package base paths to exclude
236 * @return array List of packages
237 */
238 protected function getPackageKeysInBasePath(array $packageStateConfiguration, $basePath, array $excludedPaths = array()) {
239 $packageKeys = array();
240 foreach ($packageStateConfiguration as $packageKey => $package) {
241 if (($basePath === '' || strpos($package['packagePath'], $basePath) === 0)) {
242 $isExcluded = FALSE;
243 foreach ($excludedPaths as $excludedPath) {
244 if (strpos($package['packagePath'], $excludedPath) === 0) {
245 $isExcluded = TRUE;
246 break;
247 }
248 }
249 if (!$isExcluded) {
250 $packageKeys[] = $packageKey;
251 }
252 }
253 }
254 return $packageKeys;
255 }
256
257 }