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             $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             }
 244             $subPath = $this->findPathInGraph($graph, $node, $to);
 245             if (!empty($subPath)) {
 246                 array_unshift($subPath, $from);
 247                 return $subPath;
 248             }
 249         }
 250         return [];
 251     }
 252
 253     /**
 254      * Prepare dependencies
 255      *
 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
 259      *
 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
 264      */
 265     protected function prepareDependencies(array $dependencies, $beforeKey = 'before', $afterKey = 'after')
 266     {
 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] = [];
 272                 }
 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] = [
 277                             $beforeKey => [],
 278                             $afterKey => []
 279                         ];
 280                     }
 281                 }
 282             }
 283             $preparedDependencies[$id] = $dependency;
 284         }
 285         return $preparedDependencies;
 286     }
 287 }