2 namespace TYPO3\CMS\Core\Service;
52 $graph = $this->buildDependencyGraph($items, $beforeKey, $afterKey);
55 if (isset($items[$id])) {
56 $sortedItems[$id] = $items[$id];
88 public function buildDependencyGraph(array $dependencies, $beforeKey =
'before', $afterKey =
'after')
92 $identifiers = array_keys($dependencies);
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;
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;
134 $rootIds = array_flip($this->
findRootIds($dependencyGraph));
137 foreach ($rootIds as $id => &$dependencies) {
138 $dependencies = count(array_filter($dependencyGraph[$id]));
140 unset($dependencies);
147 while (!empty($rootIds)) {
150 $minimum = PHP_INT_MAX;
152 foreach ($rootIds as $id => $count) {
153 if ($count <= $minimum) {
158 unset($rootIds[$currentId]);
160 array_push($sortedIds, $currentId);
163 foreach (array_filter($dependencyGraph[$currentId]) as $dependingId => $_) {
165 $dependencyGraph[$currentId][$dependingId] =
false;
168 $rootIds[$dependingId] = count(array_filter($dependencyGraph[$dependingId]));
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);
188 return array_reverse($sortedIds);
200 $incomingEdgeCount = 0;
201 foreach ($dependencyGraph as $dependencies) {
202 if ($dependencies[$identifier]) {
203 $incomingEdgeCount++;
206 return $incomingEdgeCount;
222 foreach ($dependencyGraph as $id => $_) {
240 foreach (array_filter($graph[$from]) as $node => $_) {
242 return array($from, $to);
245 if (!empty($subPath)) {
246 array_unshift($subPath, $from);
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] = [];
275 foreach ($dependency[$relation] as $dependingId) {
276 if (!isset($dependencies[$dependingId]) && !isset($preparedDependencies[$dependingId])) {
277 $preparedDependencies[$dependingId] = [
284 $preparedDependencies[$id] = $dependency;
286 return $preparedDependencies;