TYPO3CMS  8
 All Classes Namespaces Files Functions Variables Pages
DependencyOrderingService.php
Go to the documentation of this file.
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 
31 {
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 
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)
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 
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 
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 
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 
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 
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 }
prepareDependencies(array $dependencies, $beforeKey= 'before', $afterKey= 'after')
getIncomingEdgeCount(array $dependencyGraph, $identifier)
orderByDependencies(array $items, $beforeKey= 'before', $afterKey= 'after')