418ebc2f57dc2a5ffee8519b7b7acbf07f852647
[Packages/TYPO3.CMS.git] / typo3 / sysext / core / Classes / Service / DependencyOrderingService.php
1 <?php
2 namespace TYPO3\CMS\Core\Service;
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 provides functionality to build
19 * an ordered list from a set of dependencies.
20 *
21 * We use an adjacency matrix for the dependency graph (DAG)
22 *
23 * Example structure of the DAG is:
24 * A => (A => FALSE, B => TRUE, C => FALSE)
25 * B => (A => FALSE, B => FALSE, C => FALSE)
26 * C => (A => TRUE, B => FALSE, C => FALSE)
27 *
28 * A depends on B, C depends on A, B is independent
29 */
30 class DependencyOrderingService
31 {
32 /**
33 * Order items by specified dependencies before/after
34 *
35 * The dependencies of an items are specified as:
36 * 'someItemKey' => [
37 * 'before' => ['someItemKeyA', 'someItemKeyB']
38 * 'after' => ['someItemKeyC']
39 * ]
40 *
41 * If your items use different keys for specifying the relations, you can define the appropriate keys
42 * by setting the $beforeKey and $afterKey parameters accordingly.
43 *
44 * @param array $items
45 * @param string $beforeKey The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
46 * @param string $afterKey The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
47 * @return array
48 * @throws \UnexpectedValueException
49 */
50 public function orderByDependencies(array $items, $beforeKey = 'before', $afterKey = 'after')
51 {
52 $graph = $this->buildDependencyGraph($items, $beforeKey, $afterKey);
53 $sortedItems = [];
54 foreach ($this->calculateOrder($graph) as $id) {
55 if (isset($items[$id])) {
56 $sortedItems[$id] = $items[$id];
57 }
58 }
59 return $sortedItems;
60 }
61
62 /**
63 * Builds the dependency graph for the given dependencies
64 *
65 * The dependencies have to specified in the following structure:
66 * $dependencies = [
67 * 'someKey' => [
68 * 'before' => ['someKeyA', 'someKeyB']
69 * 'after' => ['someKeyC']
70 * ]
71 * ]
72 *
73 * We interpret a dependency like
74 * 'A' => [
75 * 'before' => ['B'],
76 * 'after' => ['C', 'D']
77 * ]
78 * as
79 * - A depends on C
80 * - A depends on D
81 * - B depends on A
82 *
83 * @param array $dependencies
84 * @param string $beforeKey The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
85 * @param string $afterKey The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
86 * @return \bool[][] The dependency graph
87 */
88 public function buildDependencyGraph(array $dependencies, $beforeKey = 'before', $afterKey = 'after')
89 {
90 $dependencies = $this->prepareDependencies($dependencies, $beforeKey, $afterKey);
91
92 $identifiers = array_keys($dependencies);
93 sort($identifiers);
94 // $dependencyGraph is the adjacency matrix as two-dimensional array initialized to FALSE (empty graph)
95 /** @var bool[][] $dependencyGraph */
96 $dependencyGraph = array_fill_keys($identifiers, array_fill_keys($identifiers, false));
97
98 foreach ($identifiers as $id) {
99 foreach ($dependencies[$id][$beforeKey] as $beforeId) {
100 $dependencyGraph[$beforeId][$id] = true;
101 }
102 foreach ($dependencies[$id][$afterKey] as $afterId) {
103 $dependencyGraph[$id][$afterId] = true;
104 }
105 }
106
107 // @internal DependencyResolver
108 // this is a dirty special case for suggestion handling of packages
109 // see \TYPO3\CMS\Core\Package\DependencyResolver::convertConfigurationForGraph for details
110 // DO NOT use this for any other case
111 foreach ($identifiers as $id) {
112 if (isset($dependencies[$id]['after-resilient'])) {
113 foreach ($dependencies[$id]['after-resilient'] as $afterId) {
114 $reverseDependencies = $this->findPathInGraph($dependencyGraph, $afterId, $id);
115 if (empty($reverseDependencies)) {
116 $dependencyGraph[$id][$afterId] = true;
117 }
118 }
119 }
120 }
121
122 return $dependencyGraph;
123 }
124
125 /**
126 * Calculate an ordered list for a dependencyGraph
127 *
128 * @param bool[][] $dependencyGraph
129 * @return mixed[] Sorted array of keys of $dependencies
130 * @throws \UnexpectedValueException
131 */
132 public function calculateOrder(array $dependencyGraph)
133 {
134 $rootIds = array_flip($this->findRootIds($dependencyGraph));
135
136 // Add number of dependencies for each root node
137 foreach ($rootIds as $id => &$dependencies) {
138 $dependencies = count(array_filter($dependencyGraph[$id]));
139 }
140 unset($dependencies);
141
142 // This will contain our final result in reverse order,
143 // meaning a result of [A, B, C] equals "A after B after C"
144 $sortedIds = [];
145
146 // Walk through the graph, level by level
147 while (!empty($rootIds)) {
148 ksort($rootIds);
149 // We take those with fewer dependencies first, to have them at the end of the list in the final result.
150 $minimum = PHP_INT_MAX;
151 $currentId = 0;
152 foreach ($rootIds as $id => $count) {
153 if ($count <= $minimum) {
154 $minimum = $count;
155 $currentId = $id;
156 }
157 }
158 unset($rootIds[$currentId]);
159
160 array_push($sortedIds, $currentId);
161
162 // Process the dependencies of the current node
163 foreach (array_filter($dependencyGraph[$currentId]) as $dependingId => $_) {
164 // Remove the edge to this dependency
165 $dependencyGraph[$currentId][$dependingId] = false;
166 if (!$this->getIncomingEdgeCount($dependencyGraph, $dependingId)) {
167 // We found a new root, lets add it to the list
168 $rootIds[$dependingId] = count(array_filter($dependencyGraph[$dependingId]));
169 }
170 }
171 }
172
173 // Check for remaining edges in the graph
174 $cycles = [];
175 array_walk($dependencyGraph, function ($dependencies, $fromId) use (&$cycles) {
176 array_walk($dependencies, function ($dependency, $toId) use (&$cycles, $fromId) {
177 if ($dependency) {
178 $cycles[] = $fromId . '->' . $toId;
179 }
180 });
181 });
182 if (!empty($cycles)) {
183 throw new \UnexpectedValueException('Your dependencies have cycles. That will not work out. Cycles found: ' . implode(', ', $cycles), 1381960494);
184 }
185
186 // We now built a list of dependencies
187 // Reverse the list to get the correct sorting order
188 return array_reverse($sortedIds);
189 }
190
191 /**
192 * Get the number of incoming edges in the dependency graph for given identifier
193 *
194 * @param array $dependencyGraph
195 * @param string $identifier
196 * @return int
197 */
198 protected function getIncomingEdgeCount(array $dependencyGraph, $identifier)
199 {
200 $incomingEdgeCount = 0;
201 foreach ($dependencyGraph as $dependencies) {
202 if ($dependencies[$identifier]) {
203 $incomingEdgeCount++;
204 }
205 }
206 return $incomingEdgeCount;
207 }
208
209 /**
210 * Find all root nodes of a graph
211 *
212 * Root nodes are those, where nothing else depends on (they can be the last in the loading order).
213 * If there are no dependencies at all, all nodes are root nodes.
214 *
215 * @param bool[][] $dependencyGraph
216 * @return array List of identifiers which are root nodes
217 */
218 public function findRootIds(array $dependencyGraph)
219 {
220 // Filter nodes with no incoming edge (aka root nodes)
221 $rootIds = [];
222 foreach ($dependencyGraph as $id => $_) {
223 if (!$this->getIncomingEdgeCount($dependencyGraph, $id)) {
224 $rootIds[] = $id;
225 }
226 }
227 return $rootIds;
228 }
229
230 /**
231 * Find any path in the graph from given start node to destination node
232 *
233 * @param array $graph Directed graph
234 * @param string $from Start node
235 * @param string $to Destination node
236 * @return array Nodes of the found path; empty if no path is found
237 */
238 protected function findPathInGraph(array $graph, $from, $to)
239 {
240 foreach (array_filter($graph[$from]) as $node => $_) {
241 if ($node === $to) {
242 return [$from, $to];
243 } else {
244 $subPath = $this->findPathInGraph($graph, $node, $to);
245 if (!empty($subPath)) {
246 array_unshift($subPath, $from);
247 return $subPath;
248 }
249 }
250 }
251 return [];
252 }
253
254 /**
255 * Prepare dependencies
256 *
257 * Ensure that all discovered identifiers are added to the dependency list
258 * so we can reliably use the identifiers to build the matrix.
259 * Additionally fix all invalid or missing before/after arrays
260 *
261 * @param array $dependencies
262 * @param string $beforeKey The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
263 * @param string $afterKey The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
264 * @return array Prepared dependencies
265 */
266 protected function prepareDependencies(array $dependencies, $beforeKey = 'before', $afterKey = 'after')
267 {
268 $preparedDependencies = [];
269 foreach ($dependencies as $id => $dependency) {
270 foreach ([ $beforeKey, $afterKey ] as $relation) {
271 if (!isset($dependency[$relation]) || !is_array($dependency[$relation])) {
272 $dependency[$relation] = [];
273 }
274 // add all missing, but referenced identifiers to the $dependency list
275 foreach ($dependency[$relation] as $dependingId) {
276 if (!isset($dependencies[$dependingId]) && !isset($preparedDependencies[$dependingId])) {
277 $preparedDependencies[$dependingId] = [
278 $beforeKey => [],
279 $afterKey => []
280 ];
281 }
282 }
283 }
284 $preparedDependencies[$id] = $dependency;
285 }
286 return $preparedDependencies;
287 }
288 }