2 namespace TYPO3\CMS\Core\Service
;
5 * This file is part of the TYPO3 CMS project.
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.
11 * For the full copyright and license information, please read the
12 * LICENSE.txt file that was distributed with this source code.
14 * The TYPO3 project - inspiring people to share!
18 * This class provides functionality to build
19 * an ordered list from a set of dependencies.
21 * We use an adjacency matrix for the dependency graph (DAG)
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)
28 * A depends on B, C depends on A, B is independent
30 class DependencyOrderingService
33 * Order items by specified dependencies before/after
35 * The dependencies of an items are specified as:
37 * 'before' => ['someItemKeyA', 'someItemKeyB']
38 * 'after' => ['someItemKeyC']
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.
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'
48 * @throws \UnexpectedValueException
50 public function orderByDependencies(array $items, $beforeKey = 'before', $afterKey = 'after')
52 $graph = $this->buildDependencyGraph($items, $beforeKey, $afterKey);
54 foreach ($this->calculateOrder($graph) as $id) {
55 if (isset($items[$id])) {
56 $sortedItems[$id] = $items[$id];
63 * Builds the dependency graph for the given dependencies
65 * The dependencies have to specified in the following structure:
68 * 'before' => ['someKeyA', 'someKeyB']
69 * 'after' => ['someKeyC']
73 * We interpret a dependency like
76 * 'after' => ['C', 'D']
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
88 public function buildDependencyGraph(array $dependencies, $beforeKey = 'before', $afterKey = 'after')
90 $dependencies = $this->prepareDependencies($dependencies, $beforeKey, $afterKey);
92 $identifiers = array_keys($dependencies);
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));
98 foreach ($identifiers as $id) {
99 foreach ($dependencies[$id][$beforeKey] as $beforeId) {
100 $dependencyGraph[$beforeId][$id] = true;
102 foreach ($dependencies[$id][$afterKey] as $afterId) {
103 $dependencyGraph[$id][$afterId] = true;
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;
122 return $dependencyGraph;
126 * Calculate an ordered list for a dependencyGraph
128 * @param bool[][] $dependencyGraph
129 * @return mixed[] Sorted array of keys of $dependencies
130 * @throws \UnexpectedValueException
132 public function calculateOrder(array $dependencyGraph)
134 $rootIds = array_flip($this->findRootIds($dependencyGraph));
136 // Add number of dependencies for each root node
137 foreach ($rootIds as $id => &$dependencies) {
138 $dependencies = count(array_filter($dependencyGraph[$id]));
140 unset($dependencies);
142 // This will contain our final result in reverse order,
143 // meaning a result of [A, B, C] equals "A after B after C"
146 // Walk through the graph, level by level
147 while (!empty($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
;
152 foreach ($rootIds as $id => $count) {
153 if ($count <= $minimum) {
158 unset($rootIds[$currentId]);
160 $sortedIds[] = $currentId;
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]));
173 // Check for remaining edges in the graph
175 array_walk($dependencyGraph, function ($dependencies, $fromId) use (&$cycles) {
176 array_walk($dependencies, function ($dependency, $toId) use (&$cycles, $fromId) {
178 $cycles[] = $fromId . '->' . $toId;
182 if (!empty($cycles)) {
183 throw new \
UnexpectedValueException('Your dependencies have cycles. That will not work out. Cycles found: ' . implode(', ', $cycles), 1381960494);
186 // We now built a list of dependencies
187 // Reverse the list to get the correct sorting order
188 return array_reverse($sortedIds);
192 * Get the number of incoming edges in the dependency graph for given identifier
194 * @param array $dependencyGraph
195 * @param string $identifier
198 protected function getIncomingEdgeCount(array $dependencyGraph, $identifier)
200 $incomingEdgeCount = 0;
201 foreach ($dependencyGraph as $dependencies) {
202 if ($dependencies[$identifier]) {
203 $incomingEdgeCount++
;
206 return $incomingEdgeCount;
210 * Find all root nodes of a graph
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.
215 * @param bool[][] $dependencyGraph
216 * @return array List of identifiers which are root nodes
218 public function findRootIds(array $dependencyGraph)
220 // Filter nodes with no incoming edge (aka root nodes)
222 foreach ($dependencyGraph as $id => $_) {
223 if (!$this->getIncomingEdgeCount($dependencyGraph, $id)) {
231 * Find any path in the graph from given start node to destination node
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
238 protected function findPathInGraph(array $graph, $from, $to)
240 foreach (array_filter($graph[$from]) as $node => $_) {
244 $subPath = $this->findPathInGraph($graph, $node, $to);
245 if (!empty($subPath)) {
246 array_unshift($subPath, $from);
254 * Prepare dependencies
256 * Ensure that all discovered identifiers are added to the dependency list
257 * so we can reliably use the identifiers to build the matrix.
258 * Additionally fix all invalid or missing before/after arrays
260 * @param array $dependencies
261 * @param string $beforeKey The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
262 * @param string $afterKey The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
263 * @return array Prepared dependencies
265 protected function prepareDependencies(array $dependencies, $beforeKey = 'before', $afterKey = 'after')
267 $preparedDependencies = [];
268 foreach ($dependencies as $id => $dependency) {
269 foreach ([$beforeKey, $afterKey] as $relation) {
270 if (!isset($dependency[$relation]) ||
!is_array($dependency[$relation])) {
271 $dependency[$relation] = [];
273 // add all missing, but referenced identifiers to the $dependency list
274 foreach ($dependency[$relation] as $dependingId) {
275 if (!isset($dependencies[$dependingId]) && !isset($preparedDependencies[$dependingId])) {
276 $preparedDependencies[$dependingId] = [
283 $preparedDependencies[$id] = $dependency;
285 return $preparedDependencies;