[FEATURE] Extract dependency ordering out of DependencyResolver 55/39955/13
authorMarkus Klein <markus.klein@typo3.org>
Thu, 4 Jun 2015 20:34:33 +0000 (22:34 +0200)
committerBenjamin Mack <benni@typo3.org>
Mon, 29 Jun 2015 13:59:01 +0000 (15:59 +0200)
The DependencyOrderingService allows to resolve dependency lists
containing before/after dependency specifications into an ordered
list. This is useful for all sorts of registration APIs like hooks.

The code is extracted from the existing DependencyResolver for packages.
The DependencyResolver is adjusted to use the DepencyOrderingService.

Resolves: #67293
Releases: master
Change-Id: Ic4cb1c7cfbcc8c4a0ebe2946eb5824d7983e711c
Reviewed-on: http://review.typo3.org/39955
Reviewed-by: Christian Kuhn <lolli@schwarzbu.ch>
Tested-by: Christian Kuhn <lolli@schwarzbu.ch>
Reviewed-by: Xavier Perseguers <xavier@typo3.org>
Tested-by: Xavier Perseguers <xavier@typo3.org>
Reviewed-by: Benjamin Mack <benni@typo3.org>
Tested-by: Benjamin Mack <benni@typo3.org>
typo3/sysext/core/Classes/Package/DependencyResolver.php
typo3/sysext/core/Classes/Service/DependencyOrderingService.php [new file with mode: 0644]
typo3/sysext/core/Documentation/Changelog/master/Feature-67293-DependencyOrderingService.rst [new file with mode: 0644]
typo3/sysext/core/Tests/Unit/Package/DependencyResolverTest.php
typo3/sysext/core/Tests/Unit/Package/PackageManagerTest.php
typo3/sysext/core/Tests/Unit/Service/DependencyOrderingServiceTest.php [new file with mode: 0644]

index d3a961c..635110c 100644 (file)
@@ -13,14 +13,16 @@ namespace TYPO3\CMS\Core\Package;
  *
  * The TYPO3 project - inspiring people to share!
  */
+
 use TYPO3\CMS\Core\Core\Bootstrap;
+use TYPO3\CMS\Core\Service\DependencyOrderingService;
 
 /**
  * This class takes care about dependencies between packages.
  * It provides functionality to resolve dependencies and to determine
  * the crucial loading order of the packages.
  *
- * @author Markus Klein <klein.t3@mfc-linz.at>
+ * @author Markus Klein <markus.klein@typo3.org>
  */
 class DependencyResolver {
 
@@ -30,69 +32,30 @@ class DependencyResolver {
        const SYSEXT_FOLDER = 'typo3/sysext';
 
        /**
+        * @var DependencyOrderingService
+        */
+       protected $dependencyOrderingService;
+
+       /**
+        * @param DependencyOrderingService $dependencyOrderingService
+        */
+       public function injectDependencyOrderingService(DependencyOrderingService $dependencyOrderingService) {
+               $this->dependencyOrderingService = $dependencyOrderingService;
+       }
+
+       /**
         * @param array $packageStatesConfiguration
         * @return array Returns the packageStatesConfiguration sorted by dependencies
         * @throws \UnexpectedValueException
         */
        public function sortPackageStatesConfigurationByDependency(array $packageStatesConfiguration) {
                // We just want to consider active packages
-               $activePackageStatesConfiguration = $this->removeInactivePackagesFromPackageStateConfiguration($packageStatesConfiguration);
-               $inactivePackageStatesConfiguration = array_diff_key($packageStatesConfiguration, $activePackageStatesConfiguration);
-
-               /*
-                * Adjacency matrix for the dependency graph (DAG)
-                *
-                * Example structure is:
-                *    A => (A => FALSE, B => TRUE,  C => FALSE)
-                *    B => (A => FALSE, B => FALSE, C => FALSE)
-                *    C => (A => TRUE,  B => FALSE, C => FALSE)
-                *
-                *    A depends on B, C depends on A, B is independent
-                */
-               $dependencyGraph = $this->buildDependencyGraph($activePackageStatesConfiguration);
-
-               // Filter extensions with no incoming edge
-               $rootPackageKeys = array();
-               foreach ($dependencyGraph as $packageKey => $_) {
-                       if (!$this->getIncomingEdgeCount($dependencyGraph, $packageKey)) {
-                               $rootPackageKeys[] = $packageKey;
-                       }
-               }
-
-               // This will contain our final result
-               $sortedPackageKeys = array();
-
-               // Walk through the graph
-               while (count($rootPackageKeys)) {
-                       $currentPackageKey = array_shift($rootPackageKeys);
-                       array_push($sortedPackageKeys, $currentPackageKey);
-
-                       foreach (array_filter($dependencyGraph[$currentPackageKey]) as $dependingPackageKey => $_) {
-                               // Remove the edge to this dependency
-                               $dependencyGraph[$currentPackageKey][$dependingPackageKey] = FALSE;
-                               if (!$this->getIncomingEdgeCount($dependencyGraph, $dependingPackageKey)) {
-                                       // We found a new root, lets add it
-                                       array_unshift($rootPackageKeys, $dependingPackageKey);
-                               }
-                       }
-               }
-
-               // Check for remaining edges in the graph
-               $cycles = array();
-               array_walk($dependencyGraph, function($dependencies, $packageKeyFrom) use(&$cycles) {
-                       array_walk($dependencies, function($dependency, $packageKeyTo) use(&$cycles, $packageKeyFrom) {
-                               if ($dependency) {
-                                       $cycles[] = $packageKeyFrom . '->' . $packageKeyTo;
-                               }
-                       });
+               $activePackageStatesConfiguration = array_filter($packageStatesConfiguration, function($packageState) {
+                       return isset($packageState['state']) && $packageState['state'] === 'active';
                });
-               if (count($cycles)) {
-                       throw new \UnexpectedValueException('Your dependencies have cycles. That will not work out. Cycles found: ' . implode(', ', $cycles), 1381960493);
-               }
+               $inactivePackageStatesConfiguration = array_diff_key($packageStatesConfiguration, $activePackageStatesConfiguration);
 
-               // We built now a list of dependencies
-               // Reverse the list to get the correct loading order
-               $sortedPackageKeys = array_reverse($sortedPackageKeys);
+               $sortedPackageKeys = $this->dependencyOrderingService->calculateOrder($this->buildDependencyGraph($activePackageStatesConfiguration));
 
                // Reorder the package states according to the loading order
                $newPackageStatesConfiguration = array();
@@ -107,104 +70,64 @@ class DependencyResolver {
        }
 
        /**
-        * Returns only active package state configurations
+        * Convert the package configuration into a dependency definition
         *
-        * @param array $packageStatesConfiguration
-        * @return array
-        */
-       protected function removeInactivePackagesFromPackageStateConfiguration(array $packageStatesConfiguration) {
-               return array_filter($packageStatesConfiguration, function($packageState) {
-                       return isset($packageState['state']) && $packageState['state'] === 'active';
-               });
-       }
-
-       /**
-        * Build the dependency graph for the given packages
+        * This converts "dependencies" and "suggestions" to "after" syntax for the usage in DependencyOrderingService
         *
         * @param array $packageStatesConfiguration
         * @param array $packageKeys
         * @return array
         * @throws \UnexpectedValueException
         */
-       protected function buildDependencyGraphForPackages(array $packageStatesConfiguration, array $packageKeys) {
-               // Initialize the dependencies with FALSE
-               sort($packageKeys);
-               $dependencyGraph = array_fill_keys($packageKeys, array_fill_keys($packageKeys, FALSE));
+       protected function convertConfigurationForGraph(array $packageStatesConfiguration, array $packageKeys) {
+               $dependencies = [];
                foreach ($packageKeys as $packageKey) {
-                       if (!isset($packageStatesConfiguration[$packageKey]['dependencies'])) {
+                       if (!isset($packageStatesConfiguration[$packageKey]['dependencies']) && !isset($packageStatesConfiguration[$packageKey]['suggestions']) ) {
                                continue;
                        }
-                       $dependentPackageKeys = $packageStatesConfiguration[$packageKey]['dependencies'];
-                       foreach ($dependentPackageKeys as $dependentPackageKey) {
-                               if (!in_array($dependentPackageKey, $packageKeys)) {
-                                       throw new \UnexpectedValueException(
-                                               'The package "' . $packageKey . '" depends on "'
-                                               . $dependentPackageKey . '" which is not present in the system.',
-                                               1382276561);
+                       $dependencies[$packageKey] = [
+                               'after' => []
+                       ];
+                       if (isset($packageStatesConfiguration[$packageKey]['dependencies'])) {
+                               foreach ($packageStatesConfiguration[$packageKey]['dependencies'] as $dependentPackageKey) {
+                                       if (!in_array($dependentPackageKey, $packageKeys, TRUE)) {
+                                               throw new \UnexpectedValueException(
+                                                       'The package "' . $packageKey . '" depends on "'
+                                                       . $dependentPackageKey . '" which is not present in the system.',
+                                                       1382276561);
+                                       }
+                                       $dependencies[$packageKey]['after'][] = $dependentPackageKey;
                                }
-                               $dependencyGraph[$packageKey][$dependentPackageKey] = TRUE;
                        }
-               }
-               foreach ($packageKeys as $packageKey) {
-                       if (!isset($packageStatesConfiguration[$packageKey]['suggestions'])) {
-                               continue;
-                       }
-                       $suggestedPackageKeys = $packageStatesConfiguration[$packageKey]['suggestions'];
-                       foreach ($suggestedPackageKeys as $suggestedPackageKey) {
-                               if (!in_array($suggestedPackageKey, $packageKeys)) {
-                                       continue;
-                               }
-                               // Check if there's no dependency of the suggestion to the package
-                               // Dependencies take precedence over suggestions
-                               $dependencies = $this->findPathInGraph($dependencyGraph, $suggestedPackageKey, $packageKey);
-                               if (empty($dependencies)) {
-                                       $dependencyGraph[$packageKey][$suggestedPackageKey] = TRUE;
+                       if (isset($packageStatesConfiguration[$packageKey]['suggestions'])) {
+                               foreach ($packageStatesConfiguration[$packageKey]['suggestions'] as $suggestedPackageKey) {
+                                       // skip suggestions on not existing packages
+                                       if (in_array($suggestedPackageKey, $packageKeys, TRUE)) {
+                                               // Suggestions actually have never been meant to influence loading order.
+                                               // We misuse this currently, as there is no other way to influence the loading order
+                                               // for not-required packages (soft-dependency).
+                                               // When considering suggestions for the loading order, we might create a cyclic dependency
+                                               // if the suggested package already has a real dependency on this package, so the suggestion
+                                               // has do be dropped in this case and must *not* be taken into account for loading order evaluation.
+                                               $dependencies[$packageKey]['after-resilient'][] = $suggestedPackageKey;
+                                       }
                                }
                        }
                }
-               return $dependencyGraph;
+               return $dependencies;
        }
 
        /**
-        * Find any path in the graph from given start node to destination node
+        * Adds all root packages of current dependency graph as dependency to all extensions
         *
-        * @param array $graph Directed graph
-        * @param string $from Start node
-        * @param string $to Destination node
-        * @return array Nodes of the found path; empty if no path is found
-        */
-       protected function findPathInGraph(array $graph, $from, $to) {
-               foreach (array_filter($graph[$from]) as $node => $_) {
-                       if ($node === $to) {
-                               return array($from, $to);
-                       } else {
-                               $subPath = $this->findPathInGraph($graph, $node, $to);
-                               if (!empty($subPath)) {
-                                       array_unshift($subPath, $from);
-                                       return $subPath;
-                               }
-                       }
-               }
-               return array();
-       }
-
-       /**
-        * Adds all root packages of current dependency graph as dependency
-        * to all extensions.
         * This ensures that the framework extensions (aka sysext) are
         * always loaded first, before any other external extension.
         *
         * @param array $packageStateConfiguration
-        * @param array $dependencyGraph
+        * @param array $rootPackageKeys
         * @return array
         */
-       protected function addDependencyToFrameworkToAllExtensions(array $packageStateConfiguration, array $dependencyGraph) {
-               $rootPackageKeys = array();
-               foreach ($dependencyGraph as $packageKey => $_) {
-                       if (!$this->getIncomingEdgeCount($dependencyGraph, $packageKey)) {
-                               $rootPackageKeys[] = $packageKey;
-                       }
-               }
+       protected function addDependencyToFrameworkToAllExtensions(array $packageStateConfiguration, array $rootPackageKeys) {
                $frameworkPackageKeys = $this->findFrameworkPackages($packageStateConfiguration);
                $extensionPackageKeys = array_diff(array_keys($packageStateConfiguration), $frameworkPackageKeys);
                foreach ($extensionPackageKeys as $packageKey) {
@@ -233,12 +156,11 @@ class DependencyResolver {
         */
        protected function buildDependencyGraph(array $packageStateConfiguration) {
                $frameworkPackageKeys = $this->findFrameworkPackages($packageStateConfiguration);
-               $dependencyGraph = $this->buildDependencyGraphForPackages($packageStateConfiguration, $frameworkPackageKeys);
-               $packageStateConfiguration = $this->addDependencyToFrameworkToAllExtensions($packageStateConfiguration, $dependencyGraph);
+               $frameworkPackagesDependencyGraph = $this->dependencyOrderingService->buildDependencyGraph($this->convertConfigurationForGraph($packageStateConfiguration, $frameworkPackageKeys));
+               $packageStateConfiguration = $this->addDependencyToFrameworkToAllExtensions($packageStateConfiguration, $this->dependencyOrderingService->findRootIds($frameworkPackagesDependencyGraph));
 
                $packageKeys = array_keys($packageStateConfiguration);
-               $dependencyGraph = $this->buildDependencyGraphForPackages($packageStateConfiguration, $packageKeys);
-               return $dependencyGraph;
+               return $this->dependencyOrderingService->buildDependencyGraph($this->convertConfigurationForGraph($packageStateConfiguration, $packageKeys));
        }
 
        /**
@@ -253,7 +175,14 @@ class DependencyResolver {
                foreach ($packageStateConfiguration as $packageKey => $packageConfiguration) {
                        /** @var Package $package */
                        $package = $packageManager->getPackage($packageKey);
-                       if ($package instanceof Package && ($package->isPartOfFactoryDefault() || $package->isPartOfMinimalUsableSystem() || strpos($packageConfiguration['packagePath'], self::SYSEXT_FOLDER) === 0)) {
+                       if (
+                               $package instanceof Package
+                               && (
+                                       $package->isPartOfFactoryDefault()
+                                       || $package->isPartOfMinimalUsableSystem()
+                                       || strpos($packageConfiguration['packagePath'], self::SYSEXT_FOLDER) === 0
+                               )
+                       ) {
                                $frameworkPackageKeys[] = $packageKey;
                        }
                }
@@ -261,22 +190,4 @@ class DependencyResolver {
                return $frameworkPackageKeys;
        }
 
-       /**
-        * Get the number of incoming edges in the dependency graph
-        * for given package key.
-        *
-        * @param array $dependencyGraph
-        * @param string $packageKey
-        * @return int
-        */
-       protected function getIncomingEdgeCount(array $dependencyGraph, $packageKey) {
-               $incomingEdgeCount = 0;
-               foreach ($dependencyGraph as $dependencies) {
-                       if ($dependencies[$packageKey]) {
-                               $incomingEdgeCount++;
-                       }
-               }
-               return $incomingEdgeCount;
-       }
-
 }
diff --git a/typo3/sysext/core/Classes/Service/DependencyOrderingService.php b/typo3/sysext/core/Classes/Service/DependencyOrderingService.php
new file mode 100644 (file)
index 0000000..ef7714b
--- /dev/null
@@ -0,0 +1,262 @@
+<?php
+namespace TYPO3\CMS\Core\Service;
+
+/*
+ * This file is part of the TYPO3 CMS project.
+ *
+ * It is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License, either version 2
+ * of the License, or any later version.
+ *
+ * For the full copyright and license information, please read the
+ * LICENSE.txt file that was distributed with this source code.
+ *
+ * The TYPO3 project - inspiring people to share!
+ */
+
+/**
+ * This class provides functionality to build
+ * an ordered list from a set of dependencies.
+ *
+ * We use an adjacency matrix for the dependency graph (DAG)
+ *
+ * Example structure of the DAG is:
+ *    A => (A => FALSE, B => TRUE,  C => FALSE)
+ *    B => (A => FALSE, B => FALSE, C => FALSE)
+ *    C => (A => TRUE,  B => FALSE, C => FALSE)
+ *
+ *    A depends on B, C depends on A, B is independent
+ *
+ * @author Markus Klein <markus.klein@typo3.org>
+ */
+class DependencyOrderingService {
+
+       /**
+        * Order items by specified dependencies before/after
+        *
+        * The dependencies of an items are specified as:
+        *   'someItemKey' => [
+        *      'before' => ['someItemKeyA', 'someItemKeyB']
+        *      'after' => ['someItemKeyC']
+        *   ]
+        *
+        * If your items use different keys for specifying the relations, you can define the appropriate keys
+        * by setting the $beforeKey and $afterKey parameters accordingly.
+        *
+        * @param array $items
+        * @param string $beforeKey The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
+        * @param string $afterKey The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
+        * @return array
+        * @throws \UnexpectedValueException
+        */
+       public function orderByDependencies(array $items, $beforeKey = 'before', $afterKey = 'after') {
+               $graph = $this->buildDependencyGraph($items, $beforeKey, $afterKey);
+               $sortedItems = [];
+               foreach ($this->calculateOrder($graph) as $id) {
+                       if (isset($items[$id])) {
+                               $sortedItems[$id] = $items[$id];
+                       }
+               }
+               return $sortedItems;
+       }
+
+       /**
+        * Builds the dependency graph for the given dependencies
+        *
+        * The dependencies have to specified in the following structure:
+        * $dependencies = [
+        *   'someKey' => [
+        *      'before' => ['someKeyA', 'someKeyB']
+        *      'after' => ['someKeyC']
+        *   ]
+        * ]
+        *
+        * We interpret a dependency like
+        *   'A' => [
+        *     'before' => ['B'],
+        *     'after' => ['C', 'D']
+        *   ]
+        * as
+        *   - A depends on C
+        *   - A depends on D
+        *   - B depends on A
+        *
+        * @param array $dependencies
+        * @param string $beforeKey The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
+        * @param string $afterKey The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
+        * @return \bool[][] The dependency graph
+        */
+       public function buildDependencyGraph(array $dependencies, $beforeKey = 'before', $afterKey = 'after') {
+               $dependencies = $this->prepareDependencies($dependencies, $beforeKey, $afterKey);
+
+               $identifiers = array_keys($dependencies);
+               sort($identifiers);
+               // $dependencyGraph is the adjacency matrix as two-dimensional array initialized to FALSE (empty graph)
+               /** @var bool[][] $dependencyGraph */
+               $dependencyGraph = array_fill_keys($identifiers, array_fill_keys($identifiers, FALSE));
+
+               foreach ($identifiers as $id) {
+                       foreach ($dependencies[$id][$beforeKey] as $beforeId) {
+                               $dependencyGraph[$beforeId][$id] = TRUE;
+                       }
+                       foreach ($dependencies[$id][$afterKey] as $afterId) {
+                               $dependencyGraph[$id][$afterId] = TRUE;
+                       }
+               }
+
+               // @internal DependencyResolver
+               // this is a dirty special case for suggestion handling of packages
+               // see \TYPO3\CMS\Core\Package\DependencyResolver::convertConfigurationForGraph for details
+               // DO NOT use this for any other case
+               foreach ($identifiers as $id) {
+                       if (isset($dependencies[$id]['after-resilient'])) {
+                               foreach ($dependencies[$id]['after-resilient'] as $afterId) {
+                                       $reverseDependencies = $this->findPathInGraph($dependencyGraph, $afterId, $id);
+                                       if (empty($reverseDependencies)) {
+                                               $dependencyGraph[$id][$afterId] = TRUE;
+                                       }
+                               }
+                       }
+               }
+
+               return $dependencyGraph;
+       }
+
+       /**
+        * Calculate an ordered list for a dependencyGraph
+        *
+        * @param bool[][] $dependencyGraph
+        * @return mixed[] Sorted array of keys of $dependencies
+        * @throws \UnexpectedValueException
+        */
+       public function calculateOrder(array $dependencyGraph) {
+               $rootIds = $this->findRootIds($dependencyGraph);
+
+               // This will contain our final result
+               $sortedIds = [];
+
+               // Walk through the graph
+               while (!empty($rootIds)) {
+                       $currentId = array_shift($rootIds);
+                       array_push($sortedIds, $currentId);
+
+                       foreach (array_filter($dependencyGraph[$currentId]) as $dependingId => $_) {
+                               // Remove the edge to this dependency
+                               $dependencyGraph[$currentId][$dependingId] = FALSE;
+                               if (!$this->getIncomingEdgeCount($dependencyGraph, $dependingId)) {
+                                       // We found a new root, lets add it
+                                       array_unshift($rootIds, $dependingId);
+                               }
+                       }
+               }
+
+               // Check for remaining edges in the graph
+               $cycles = [];
+               array_walk($dependencyGraph, function($dependencies, $fromId) use (&$cycles) {
+                       array_walk($dependencies, function($dependency, $toId) use (&$cycles, $fromId) {
+                               if ($dependency) {
+                                       $cycles[] = $fromId . '->' . $toId;
+                               }
+                       });
+               });
+               if (!empty($cycles)) {
+                       throw new \UnexpectedValueException('Your dependencies have cycles. That will not work out. Cycles found: ' . implode(', ', $cycles), 1381960494);
+               }
+
+               // We now built a list of dependencies
+               // Reverse the list to get the correct sorting order
+               return array_reverse($sortedIds);
+       }
+
+       /**
+        * Get the number of incoming edges in the dependency graph for given identifier
+        *
+        * @param array $dependencyGraph
+        * @param string $identifier
+        * @return int
+        */
+       protected function getIncomingEdgeCount(array $dependencyGraph, $identifier) {
+               $incomingEdgeCount = 0;
+               foreach ($dependencyGraph as $dependencies) {
+                       if ($dependencies[$identifier]) {
+                               $incomingEdgeCount++;
+                       }
+               }
+               return $incomingEdgeCount;
+       }
+
+       /**
+        * Find all root nodes of a graph
+        *
+        * @param bool[][] $dependencyGraph
+        * @return array List of identifiers which are root nodes
+        */
+       public function findRootIds(array $dependencyGraph) {
+               // Filter nodes with no incoming edge (aka root nodes)
+               $rootIds = array();
+               foreach ($dependencyGraph as $id => $_) {
+                       if (!$this->getIncomingEdgeCount($dependencyGraph, $id)) {
+                               $rootIds[] = $id;
+                       }
+               }
+               return $rootIds;
+       }
+
+       /**
+        * Find any path in the graph from given start node to destination node
+        *
+        * @param array $graph Directed graph
+        * @param string $from Start node
+        * @param string $to Destination node
+        * @return array Nodes of the found path; empty if no path is found
+        */
+       protected function findPathInGraph(array $graph, $from, $to) {
+               foreach (array_filter($graph[$from]) as $node => $_) {
+                       if ($node === $to) {
+                               return array($from, $to);
+                       } else {
+                               $subPath = $this->findPathInGraph($graph, $node, $to);
+                               if (!empty($subPath)) {
+                                       array_unshift($subPath, $from);
+                                       return $subPath;
+                               }
+                       }
+               }
+               return array();
+       }
+
+       /**
+        * Prepare dependencies
+        *
+        * Ensure that all discovered identifiers are added to the dependency list
+        * so we can reliably use the identifiers to build the matrix.
+        * Additionally fix all invalid or missing before/after arrays
+        *
+        * @param array $dependencies
+        * @param string $beforeKey The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
+        * @param string $afterKey The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
+        * @return array Prepared dependencies
+        */
+       protected function prepareDependencies(array $dependencies, $beforeKey = 'before', $afterKey = 'after') {
+               $preparedDependencies = [];
+               foreach ($dependencies as $id => $dependency) {
+                       foreach ([ $beforeKey, $afterKey ] as $relation) {
+                               if (!isset($dependency[$relation]) || !is_array($dependency[$relation])) {
+                                       $dependency[$relation] = [];
+                               }
+                               // add all missing, but referenced identifiers to the $dependency list
+                               foreach ($dependency[$relation] as $dependingId) {
+                                       if (!isset($dependencies[$dependingId]) && !isset($preparedDependencies[$dependingId])) {
+                                               $preparedDependencies[$dependingId] = [
+                                                       $beforeKey => [],
+                                                       $afterKey => []
+                                               ];
+                                       }
+                               }
+                       }
+                       $preparedDependencies[$id] = $dependency;
+               }
+               return $preparedDependencies;
+       }
+
+}
diff --git a/typo3/sysext/core/Documentation/Changelog/master/Feature-67293-DependencyOrderingService.rst b/typo3/sysext/core/Documentation/Changelog/master/Feature-67293-DependencyOrderingService.rst
new file mode 100644 (file)
index 0000000..4c426d0
--- /dev/null
@@ -0,0 +1,41 @@
+=============================================
+Feature: #67293 - Dependency ordering service
+=============================================
+
+Description
+===========
+
+In many cases it is necessary to establish a sorted list of items from a set of "dependencies".
+The ordered list is then used to execute actions in the given order.
+
+Some examples from the Core are:
+- Hook execution order
+- Extension loading order
+- Listing of menu items
+
+The dependencies are therefore specified in a relative manner, outlining that an item has to be executed/loaded/listed "before" or "after" some other item.
+
+Typical use case:
+
+.. code-block:: php
+
+       $GLOBALS['TYPO3_CONF_VARS']['EXTCONF']['someExt']['someHook'][<some id>] = [
+               'handler' => someClass::class,
+               'runBefore' => [ <some other ID> ],
+               'runAfter' => [ ... ],
+               ...
+       ];
+
+In order to evaluate such relative dependencies to finally have a sorted list for ``['someHook']``,
+we introduced a new helper class ``\TYPO3\CMS\Core\Service\DependencyOrderingService``, which does the evaluation work for you.
+
+Example usage:
+
+.. code-block:: php
+
+       $hooks = $GLOBALS['TYPO3_CONF_VARS']['EXTCONF']['someExt']['someHook'];
+       $sortedHooks = GeneralUtility:makeInstance(DependencyOrderingService::class)->orderByDependencies($hooks , 'runBefore', 'runAfter');
+
+``$sortedHooks`` will then contain the content of ``$hooks``, but sorted according to the dependencies.
+
+The ``DependencyOrderingService`` class also detects cycles in the dependencies and will throw an Exception in case conflicting dependencies were defined.
index 9c975ae..8fe8404 100644 (file)
@@ -15,13 +15,15 @@ namespace TYPO3\CMS\Core\Tests\Unit\Package;
  */
 
 use TYPO3\CMS\Core\Package\DependencyResolver;
+use TYPO3\CMS\Core\Tests\UnitTestCase;
+use TYPO3\CMS\Core\Service\DependencyOrderingService;
 
 /**
- * Testcase for the dependency resolver class
+ * Test case
  *
- * @author Markus Klein <klein.t3@mfc-linz.at>
+ * @author Markus Klein <markus.klein@typo3.org>
  */
-class DependencyResolverTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
+class DependencyResolverTest extends UnitTestCase {
 
        /**
         * @test
@@ -31,7 +33,9 @@ class DependencyResolverTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
         * @dataProvider buildDependencyGraphBuildsCorrectGraphDataProvider
         */
        public function buildDependencyGraphBuildsCorrectGraph(array $unsortedPackageStatesConfiguration, array $frameworkPackageKeys, array $expectedGraph) {
+               /** @var DependencyResolver|\PHPUnit_Framework_MockObject_MockObject|\TYPO3\CMS\Core\Tests\AccessibleObjectInterface $dependencyResolver */
                $dependencyResolver = $this->getAccessibleMock(DependencyResolver::class, array('findFrameworkPackages'));
+               $dependencyResolver->injectDependencyOrderingService(new DependencyOrderingService());
                $dependencyResolver->expects($this->any())->method('findFrameworkPackages')->willReturn($frameworkPackageKeys);
                $dependencyGraph = $dependencyResolver->_call('buildDependencyGraph', $unsortedPackageStatesConfiguration);
 
@@ -41,9 +45,14 @@ class DependencyResolverTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
        /**
         * @test
         * @dataProvider packageSortingDataProvider
+        * @param array $unsortedPackageStatesConfiguration
+        * @param array $frameworkPackageKeys
+        * @param array $expectedSortedPackageStatesConfiguration
         */
        public function sortPackageStatesConfigurationByDependencyMakesSureThatDependantPackagesAreStandingBeforeAPackageInTheInternalPackagesAndPackagesConfigurationArrays($unsortedPackageStatesConfiguration, $frameworkPackageKeys, $expectedSortedPackageStatesConfiguration) {
+               /** @var DependencyResolver|\PHPUnit_Framework_MockObject_MockObject|\TYPO3\CMS\Core\Tests\AccessibleObjectInterface $dependencyResolver */
                $dependencyResolver = $this->getAccessibleMock(DependencyResolver::class, array('findFrameworkPackages'));
+               $dependencyResolver->injectDependencyOrderingService(new DependencyOrderingService());
                $dependencyResolver->expects($this->any())->method('findFrameworkPackages')->willReturn($frameworkPackageKeys);
                $sortedPackageStatesConfiguration = $dependencyResolver->_call('sortPackageStatesConfigurationByDependency', $unsortedPackageStatesConfiguration);
 
@@ -52,18 +61,6 @@ class DependencyResolverTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
 
        /**
         * @test
-        * @dataProvider buildDependencyGraphForPackagesBuildsCorrectGraphDataProvider
-        */
-       public function buildDependencyGraphForPackagesBuildsCorrectGraph($packages, $expectedGraph) {
-               $dependencyResolver = $this->getAccessibleMock(DependencyResolver::class, array('findFrameworkPackages'));
-               $dependencyResolver->expects($this->any())->method('findFrameworkPackages')->willReturn(array());
-               $dependencyGraph = $dependencyResolver->_call('buildDependencyGraphForPackages', $packages, array_keys($packages));
-
-               $this->assertEquals($expectedGraph, $dependencyGraph);
-       }
-
-       /**
-        * @test
         * @expectedException \UnexpectedValueException
         */
        public function sortPackageStatesConfigurationByDependencyThrowsExceptionWhenCycleDetected() {
@@ -78,26 +75,14 @@ class DependencyResolverTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
                        ),
                );
 
+               /** @var DependencyResolver|\PHPUnit_Framework_MockObject_MockObject|\TYPO3\CMS\Core\Tests\AccessibleObjectInterface $dependencyResolver */
                $dependencyResolver = $this->getAccessibleMock(DependencyResolver::class, array('findFrameworkPackages'));
+               $dependencyResolver->injectDependencyOrderingService(new DependencyOrderingService());
                $dependencyResolver->expects($this->any())->method('findFrameworkPackages')->willReturn(array());
                $dependencyResolver->_call('sortPackageStatesConfigurationByDependency', $unsortedPackageStatesConfiguration);
        }
 
        /**
-        * @test
-        * @expectedException \UnexpectedValueException
-        */
-       public function buildDependencyGraphForPackagesThrowsExceptionWhenDependencyOnUnavailablePackageDetected() {
-               $packages = array(
-                       'A' => array(
-                               'dependencies' => array('B'),
-                       )
-               );
-               $dependencyResolver = $this->getAccessibleMock(DependencyResolver::class, array('dummy'));
-               $dependencyResolver->_call('buildDependencyGraphForPackages', $packages, array_keys($packages));
-       }
-
-       /**
         * @return array
         */
        public function buildDependencyGraphBuildsCorrectGraphDataProvider() {
@@ -529,330 +514,4 @@ class DependencyResolverTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
                );
        }
 
-       /**
-        * @return array
-        */
-       public function buildDependencyGraphForPackagesBuildsCorrectGraphDataProvider() {
-               return array(
-                       'TYPO3 Flow Packages' => array(
-                               array(
-                                       'TYPO3.Flow' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('Symfony.Component.Yaml', 'Doctrine.Common', 'Doctrine.DBAL', 'Doctrine.ORM')
-                                       ),
-                                       'Doctrine.ORM' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('Doctrine.Common', 'Doctrine.DBAL')
-                                       ),
-                                       'Doctrine.Common' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array()
-                                       ),
-                                       'Doctrine.DBAL' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('Doctrine.Common')
-                                       ),
-                                       'Symfony.Component.Yaml' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array()
-                                       ),
-                               ),
-                               array(
-                                       'TYPO3.Flow' => array(
-                                               'TYPO3.Flow' => FALSE,
-                                               'Doctrine.ORM' => TRUE,
-                                               'Doctrine.Common' => TRUE,
-                                               'Doctrine.DBAL' => TRUE,
-                                               'Symfony.Component.Yaml' => TRUE,
-                                       ),
-                                       'Doctrine.ORM' => array(
-                                               'TYPO3.Flow' => FALSE,
-                                               'Doctrine.ORM' => FALSE,
-                                               'Doctrine.Common' => TRUE,
-                                               'Doctrine.DBAL' => TRUE,
-                                               'Symfony.Component.Yaml' => FALSE,
-                                       ),
-                                       'Doctrine.Common' => array(
-                                               'TYPO3.Flow' => FALSE,
-                                               'Doctrine.ORM' => FALSE,
-                                               'Doctrine.Common' => FALSE,
-                                               'Doctrine.DBAL' => FALSE,
-                                               'Symfony.Component.Yaml' => FALSE,
-                                       ),
-                                       'Doctrine.DBAL' => array(
-                                               'TYPO3.Flow' => FALSE,
-                                               'Doctrine.ORM' => FALSE,
-                                               'Doctrine.Common' => TRUE,
-                                               'Doctrine.DBAL' => FALSE,
-                                               'Symfony.Component.Yaml' => FALSE,
-                                       ),
-                                       'Symfony.Component.Yaml' => array(
-                                               'TYPO3.Flow' => FALSE,
-                                               'Doctrine.ORM' => FALSE,
-                                               'Doctrine.Common' => FALSE,
-                                               'Doctrine.DBAL' => FALSE,
-                                               'Symfony.Component.Yaml' => FALSE,
-                                       ),
-                               ),
-                       ),
-                       'TYPO3 CMS Extensions' => array(
-                               array(
-                                       'core' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array(),
-                                       ),
-                                       'openid' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('core', 'setup')
-                                       ),
-                                       'scheduler' => array (
-                                               'state' => 'active',
-                                               'dependencies' => array('core'),
-                                       ),
-                                       'setup' => array (
-                                               'state' => 'active',
-                                               'dependencies' => array('core'),
-                                       ),
-                                       'sv' => array (
-                                               'state' => 'active',
-                                               'dependencies' => array('core'),
-                                       ),
-                               ),
-                               array(
-                                       'core' => array(
-                                               'core' => FALSE,
-                                               'setup' => FALSE,
-                                               'sv' => FALSE,
-                                               'scheduler' => FALSE,
-                                               'openid' => FALSE,
-                                       ),
-                                       'openid' => array(
-                                               'core' => TRUE,
-                                               'setup' => TRUE,
-                                               'sv' => FALSE,
-                                               'scheduler' => FALSE,
-                                               'openid' => FALSE,
-                                       ),
-                                       'scheduler' => array (
-                                               'core' => TRUE,
-                                               'setup' => FALSE,
-                                               'sv' => FALSE,
-                                               'scheduler' => FALSE,
-                                               'openid' => FALSE,
-                                       ),
-                                       'setup' => array (
-                                               'core' => TRUE,
-                                               'setup' => FALSE,
-                                               'sv' => FALSE,
-                                               'scheduler' => FALSE,
-                                               'openid' => FALSE,
-                                       ),
-                                       'sv' => array (
-                                               'core' => TRUE,
-                                               'setup' => FALSE,
-                                               'sv' => FALSE,
-                                               'scheduler' => FALSE,
-                                               'openid' => FALSE,
-                                       ),
-                               ),
-                       ),
-                       'Dummy Packages' => array(
-                               array(
-                                       'A' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('B', 'D', 'C'),
-                                       ),
-                                       'B' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array()
-                                       ),
-                                       'C' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('E')
-                                       ),
-                                       'D' => array (
-                                               'state' => 'active',
-                                               'dependencies' => array('E'),
-                                       ),
-                                       'E' => array (
-                                               'state' => 'active',
-                                               'dependencies' => array(),
-                                       ),
-                                       'F' => array (
-                                               'state' => 'active',
-                                               'dependencies' => array(),
-                                       ),
-                               ),
-                               array(
-                                       'A' => array(
-                                               'A' => FALSE,
-                                               'B' => TRUE,
-                                               'C' => TRUE,
-                                               'D' => TRUE,
-                                               'E' => FALSE,
-                                               'F' => FALSE,
-                                       ),
-                                       'B' => array(
-                                               'A' => FALSE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                               'D' => FALSE,
-                                               'E' => FALSE,
-                                               'F' => FALSE,
-                                       ),
-                                       'C' => array(
-                                               'A' => FALSE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                               'D' => FALSE,
-                                               'E' => TRUE,
-                                               'F' => FALSE,
-                                       ),
-                                       'D' => array (
-                                               'A' => FALSE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                               'D' => FALSE,
-                                               'E' => TRUE,
-                                               'F' => FALSE,
-                                       ),
-                                       'E' => array (
-                                               'A' => FALSE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                               'D' => FALSE,
-                                               'E' => FALSE,
-                                               'F' => FALSE,
-                                       ),
-                                       'F' => array (
-                                               'A' => FALSE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                               'D' => FALSE,
-                                               'E' => FALSE,
-                                               'F' => FALSE,
-                                       ),
-                               ),
-                       ),
-                       'Suggestions without reverse dependency' => array(
-                               array(
-                                       'A' => array(
-                                               'state' => 'active',
-                                               'suggestions' => array('B'),
-                                       ),
-                                       'B' => array(
-                                               'state' => 'active',
-                                       ),
-                                       'C' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('A')
-                                       ),
-                               ),
-                               array(
-                                       'A' => array(
-                                               'A' => FALSE,
-                                               'B' => TRUE,
-                                               'C' => FALSE,
-                                       ),
-                                       'B' => array(
-                                               'A' => FALSE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                       ),
-                                       'C' => array(
-                                               'A' => TRUE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                       ),
-                               ),
-                       ),
-                       'Suggestions with reverse dependency' => array(
-                               array(
-                                       'A' => array(
-                                               'state' => 'active',
-                                               'suggestions' => array('B'),
-                                       ),
-                                       'B' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('A')
-                                       ),
-                                       'C' => array(
-                                               'state' => 'active',
-                                               'dependencies' => array('A')
-                                       ),
-                               ),
-                               array(
-                                       'A' => array(
-                                               'A' => FALSE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                       ),
-                                       'B' => array(
-                                               'A' => TRUE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                       ),
-                                       'C' => array(
-                                               'A' => TRUE,
-                                               'B' => FALSE,
-                                               'C' => FALSE,
-                                       ),
-                               ),
-                       ),
-               );
-       }
-
-       /**
-        * @return array
-        */
-       public function findPathInGraphReturnsCorrectPathDataProvider() {
-               return array(
-                       'Simple path' => array(
-                               array(
-                                       'A' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => TRUE),
-                                       'B' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE),
-                                       'C' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE),
-                                       'Z' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE)
-                               ),
-                           'A', 'Z',
-                           array('A', 'Z')
-                       ),
-                       'No path' => array(
-                               array(
-                                       'A' => array('A' => FALSE, 'B' => TRUE, 'C' => FALSE, 'Z' => FALSE),
-                                       'B' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE),
-                                       'C' => array('A' => FALSE, 'B' => TRUE, 'C' => FALSE, 'Z' => FALSE),
-                                       'Z' => array('A' => FALSE, 'B' => TRUE, 'C' => FALSE, 'Z' => FALSE)
-                               ),
-                               'A', 'C',
-                               array()
-                       ),
-                       'Longer path' => array(
-                               array(
-                                       'A' => array('A' => FALSE, 'B' => TRUE, 'C' => TRUE, 'Z' => TRUE),
-                                       'B' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE),
-                                       'C' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => TRUE),
-                                       'Z' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE)
-                               ),
-                               'A', 'Z',
-                               array('A', 'C', 'Z')
-                       ),
-               );
-       }
-
-       /**
-        * @param array $graph
-        * @param string $from
-        * @param string $to
-        * @param array $expected
-        * @test
-        * @dataProvider findPathInGraphReturnsCorrectPathDataProvider
-        */
-       public function findPathInGraphReturnsCorrectPath(array $graph, $from, $to, array $expected) {
-               $dependencyResolver = $this->getAccessibleMock(DependencyResolver::class, array('dummy'));
-               $path = $dependencyResolver->_call('findPathInGraph', $graph, $from, $to);
-
-               $this->assertSame($expected, $path);
-       }
-
 }
index 7d5fac2..f36269f 100644 (file)
@@ -11,8 +11,11 @@ namespace TYPO3\CMS\Core\Tests\Unit\Package;
  * The TYPO3 project - inspiring people to share!                         *
  *                                                                        */
 
+use TYPO3\CMS\Core\Package\DependencyResolver;
 use TYPO3\CMS\Core\Package\PackageInterface;
 use org\bovigo\vfs\vfsStream;
+use TYPO3\CMS\Core\Package\PackageManager;
+use TYPO3\CMS\Core\Service\DependencyOrderingService;
 
 /**
  * Testcase for the default package manager
@@ -21,7 +24,7 @@ use org\bovigo\vfs\vfsStream;
 class PackageManagerTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
 
        /**
-        * @var \TYPO3\CMS\Core\Package\PackageManager
+        * @var PackageManager
         */
        protected $packageManager;
 
@@ -38,7 +41,7 @@ class PackageManagerTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
                $mockCache->expects($this->any())->method('set')->will($this->returnValue(TRUE));
                $mockCache->expects($this->any())->method('getBackend')->will($this->returnValue($mockCacheBackend));
                $mockCacheBackend->expects($this->any())->method('getCacheDirectory')->will($this->returnValue('vfs://Test/Cache'));
-               $this->packageManager = $this->getAccessibleMock(\TYPO3\CMS\Core\Package\PackageManager::class, array('sortAndSavePackageStates', 'sortAvailablePackagesByDependencies', 'registerAutoloadInformationInClassLoader'));
+               $this->packageManager = $this->getAccessibleMock(PackageManager::class, array('sortAndSavePackageStates', 'sortAvailablePackagesByDependencies', 'registerAutoloadInformationInClassLoader'));
 
                mkdir('vfs://Test/Packages/Application', 0700, TRUE);
                mkdir('vfs://Test/Configuration');
@@ -109,7 +112,7 @@ class PackageManagerTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
                        file_put_contents($packagePath . 'composer.json', '{"name": "' . $packageKey . '", "type": "typo3-test"}');
                }
 
-               $packageManager = $this->getAccessibleMock(\TYPO3\CMS\Core\Package\PackageManager::class, array('sortAndSavePackageStates'));
+               $packageManager = $this->getAccessibleMock(PackageManager::class, array('sortAndSavePackageStates'));
                $packageManager->_set('packagesBasePath', 'vfs://Test/Packages/');
                $packageManager->_set('packageStatesPathAndFilename', 'vfs://Test/Configuration/PackageStates.php');
 
@@ -141,12 +144,19 @@ class PackageManagerTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
                        file_put_contents($packagePath . 'ext_emconf.php', '');
                }
 
-               $packageManager = $this->getAccessibleMock(\TYPO3\CMS\Core\Package\PackageManager::class, array('dummy'));
+               /** @var PackageManager|\PHPUnit_Framework_MockObject_MockObject|\TYPO3\CMS\Core\Tests\AccessibleObjectInterface $packageManager */
+               $packageManager = $this->getAccessibleMock(PackageManager::class, array('dummy'));
                $packageManager->_set('packagesBasePaths', array('local' => 'vfs://Test/Packages/Application'));
                $packageManager->_set('packagesBasePath', 'vfs://Test/Packages/');
                $packageManager->_set('packageStatesPathAndFilename', 'vfs://Test/Configuration/PackageStates.php');
 
-               $dependencyResolver = $this->getMock(\TYPO3\CMS\Core\Package\DependencyResolver::class, array('dummy'));
+               /** @var DependencyResolver|\PHPUnit_Framework_MockObject_MockObject $dependencyResolver */
+               $dependencyResolver = $this->getMock(DependencyResolver::class);
+               $dependencyResolver
+                       ->expects($this->any())
+                       ->method('sortPackageStatesConfigurationByDependency')
+                       ->willReturnArgument(0);
+
                $packageManager->injectDependencyResolver($dependencyResolver);
 
                $packageManager->_set('packageStatesConfiguration', array(
@@ -185,12 +195,18 @@ class PackageManagerTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
                        file_put_contents($packagePath . 'ext_emconf.php', '');
                }
 
-               $packageManager = $this->getAccessibleMock(\TYPO3\CMS\Core\Package\PackageManager::class, array('dummy'));
+               $packageManager = $this->getAccessibleMock(PackageManager::class, array('dummy'));
                $packageManager->_set('packagesBasePaths', array('local' => 'vfs://Test/Packages/Application'));
                $packageManager->_set('packagesBasePath', 'vfs://Test/Packages/');
                $packageManager->_set('packageStatesPathAndFilename', 'vfs://Test/Configuration/PackageStates.php');
 
-               $dependencyResolver = $this->getMock(\TYPO3\CMS\Core\Package\DependencyResolver::class, array('dummy'));
+               /** @var DependencyResolver|\PHPUnit_Framework_MockObject_MockObject $dependencyResolver */
+               $dependencyResolver = $this->getMock(DependencyResolver::class);
+               $dependencyResolver
+                       ->expects($this->any())
+                       ->method('sortPackageStatesConfigurationByDependency')
+                       ->willReturnArgument(0);
+
                $packageManager->injectDependencyResolver($dependencyResolver);
 
                $packageManager->_set('packages', array());
@@ -322,7 +338,7 @@ class PackageManagerTest extends \TYPO3\CMS\Core\Tests\UnitTestCase {
                        )
                );
 
-               $packageManager = $this->getAccessibleMock(\TYPO3\CMS\Core\Package\PackageManager::class, array('resolvePackageDependencies'));
+               $packageManager = $this->getAccessibleMock(PackageManager::class, array('resolvePackageDependencies'));
                $packageManager->_set('packageStatesConfiguration', $packageStatesConfiguration);
 
                $this->assertEquals($packageKey, $packageManager->_call('getPackageKeyFromComposerName', $composerName));
diff --git a/typo3/sysext/core/Tests/Unit/Service/DependencyOrderingServiceTest.php b/typo3/sysext/core/Tests/Unit/Service/DependencyOrderingServiceTest.php
new file mode 100644 (file)
index 0000000..6c27ad2
--- /dev/null
@@ -0,0 +1,688 @@
+<?php
+namespace TYPO3\CMS\Core\Tests\Unit\Service;
+
+/*
+ * This file is part of the TYPO3 CMS project.
+ *
+ * It is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License, either version 2
+ * of the License, or any later version.
+ *
+ * For the full copyright and license information, please read the
+ * LICENSE.txt file that was distributed with this source code.
+ *
+ * The TYPO3 project - inspiring people to share!
+ */
+
+use TYPO3\CMS\Core\Tests\UnitTestCase;
+use TYPO3\CMS\Core\Service\DependencyOrderingService;
+
+/**
+ * Test case
+ *
+ * @author Markus Klein <markus.klein@typo3.org>
+ */
+class DependencyOrderingServiceTest extends UnitTestCase {
+
+       /**
+        * @test
+        * @dataProvider orderByDependenciesBuildsCorrectOrderDataProvider
+        * @param array $items
+        * @param array $expectedOrderedItems
+        */
+       public function orderByDependenciesBuildsCorrectOrder(array $items, $beforeKey, $afterKey, array $expectedOrderedItems) {
+               $orderedItems = (new DependencyOrderingService())->orderByDependencies($items);
+               $this->assertSame($expectedOrderedItems, $orderedItems);
+       }
+
+       /**
+        * @return array
+        */
+       public function orderByDependenciesBuildsCorrectOrderDataProvider() {
+               return [
+                       'unordered' => [
+                               [ // $items
+                                       1 => [],
+                                       2 => [],
+                               ],
+                               'before',
+                               'after',
+                               [ // $expectedOrderedItems
+                                       2 => [],
+                                       1 => [],
+                               ]
+                       ],
+                       'ordered' => [
+                               [ // $items
+                                       1 => [],
+                                       2 => [
+                                               'precedes' => [ 1 ]
+                                       ],
+                               ],
+                               'precedes',
+                               'after',
+                               [ // $expectedOrderedItems
+                                       2 => [
+                                               'precedes' => [ 1 ]
+                                       ],
+                                       1 => [],
+                               ]
+                       ],
+                       'mixed' => [
+                               [ // $items
+                                       1 => [],
+                                       2 => [
+                                               'before' => [ 1 ]
+                                       ],
+                                       3 => [
+                                               'otherProperty' => TRUE
+                                       ]
+                               ],
+                               'before',
+                               'after',
+                               [ // $expectedOrderedItems
+                                       3 => [
+                                               'otherProperty' => TRUE
+                                       ],
+                                       2 => [
+                                               'before' => [ 1 ]
+                                       ],
+                                       1 => [],
+                               ]
+                       ],
+                       'reference to non-existing' => [
+                               [ // $items
+                                       2 => [
+                                               'before' => [ 1 ],
+                                               'depends' => [ 3 ]
+                                       ],
+                                       3 => [
+                                               'otherProperty' => TRUE
+                                       ]
+                               ],
+                               'before',
+                               'depends',
+                               [ // $expectedOrderedItems
+                                       3 => [
+                                               'otherProperty' => TRUE
+                                       ],
+                                       2 => [
+                                               'before' => [ 1 ],
+                                               'depends' => [ 3 ]
+                                       ],
+                               ]
+                       ],
+               ];
+       }
+
+       /**
+        * @test
+        * @dataProvider prepareDependenciesBuildsFullIdentifierListDataProvider
+        * @param array $dependencies
+        * @param $expectedDependencies
+        * @throws \InvalidArgumentException
+        */
+       public function prepareDependenciesBuildsFullIdentifierList(array $dependencies, array $expectedDependencies) {
+               /** @var DependencyOrderingService|\PHPUnit_Framework_MockObject_MockObject|\TYPO3\CMS\Core\Tests\AccessibleObjectInterface $dependencyOrderingService */
+               $dependencyOrderingService = $this->getAccessibleMock(DependencyOrderingService::class, ['dummy']);
+               $preparedDependencies = $dependencyOrderingService->_call('prepareDependencies', $dependencies);
+               $this->assertEquals($expectedDependencies, $preparedDependencies);
+       }
+
+       /**
+        * @return array
+        */
+       public function prepareDependenciesBuildsFullIdentifierListDataProvider() {
+               return [
+                       'simple' => [
+                               [ // $dependencies
+                                       1 => [
+                                               'before' => [],
+                                               'after' => [ 2 ]
+                                       ],
+                               ],
+                               [ // $expectedDependencies
+                                       1 => [
+                                               'before' => [],
+                                               'after' => [ 2 ]
+                                       ],
+                                       2 => [
+                                               'before' => [],
+                                               'after' => [],
+                                       ]
+                               ]
+                       ],
+                       'missing before' => [
+                               [ // $dependencies
+                                       1 => [
+                                               'after' => [ 2 ]
+                                       ],
+                               ],
+                               [ // $expectedDependencies
+                                       1 => [
+                                               'before' => [],
+                                               'after' => [ 2 ]
+                                       ],
+                                       2 => [
+                                               'before' => [],
+                                               'after' => [],
+                                       ]
+                               ]
+                       ],
+               ];
+       }
+
+       /**
+        * @test
+        * @dataProvider buildDependencyGraphBuildsValidGraphDataProvider
+        * @param array $dependencies
+        * @param array $expectedGraph
+        */
+       public function buildDependencyGraphBuildsValidGraph(array $dependencies, array $expectedGraph) {
+               $graph = (new DependencyOrderingService())->buildDependencyGraph($dependencies);
+               $this->assertEquals($expectedGraph, $graph);
+       }
+
+       /**
+        * @return array
+        */
+       public function buildDependencyGraphBuildsValidGraphDataProvider() {
+               return [
+                       'graph1' => [
+                               [ // dependencies
+                                       1 => [
+                                               'before' => [],
+                                               'after' => [ 2 ]
+                                       ],
+                               ],
+                               [ // graph
+                                       1 => [
+                                               1 => FALSE,
+                                               2 => TRUE
+                                       ],
+                                       2 => [
+                                               1 => FALSE,
+                                               2 => FALSE
+                                       ],
+                               ]
+                       ],
+                       'graph2' => [
+                               [ // dependencies
+                                       1 => [
+                                               'before' => [ 3 ],
+                                               'after' => [ 2 ]
+                                       ],
+                               ],
+                               [ // graph
+                                       1 => [
+                                               1 => FALSE,
+                                               2 => TRUE,
+                                               3 => FALSE,
+                                       ],
+                                       2 => [
+                                               1 => FALSE,
+                                               2 => FALSE,
+                                               3 => FALSE,
+                                       ],
+                                       3 => [
+                                               1 => TRUE,
+                                               2 => FALSE,
+                                               3 => FALSE,
+                                       ],
+                               ]
+                       ],
+                       'graph3' => [
+                               [ // dependencies
+                                       3 => [
+                                               'before' => [],
+                                               'after' => []
+                                       ],
+                                       1 => [
+                                               'before' => [ 3 ],
+                                               'after' => [ 2 ]
+                                       ],
+                                       2 => [
+                                               'before' => [ 3 ],
+                                               'after' => []
+                                       ]
+                               ],
+                               [ // graph
+                                       1 => [
+                                               1 => FALSE,
+                                               2 => TRUE,
+                                               3 => FALSE,
+                                       ],
+                                       2 => [
+                                               1 => FALSE,
+                                               2 => FALSE,
+                                               3 => FALSE,
+                                       ],
+                                       3 => [
+                                               1 => TRUE,
+                                               2 => TRUE,
+                                               3 => FALSE,
+                                       ],
+                               ]
+                       ],
+                       'cyclic graph' => [
+                               [ // dependencies
+                                       1 => [
+                                               'before' => [ 2 ],
+                                               'after' => []
+                                       ],
+                                       2 => [
+                                               'before' => [ 1 ],
+                                               'after' => []
+                                       ]
+                               ],
+                               [ // graph
+                                       1 => [
+                                               1 => FALSE,
+                                               2 => TRUE,
+                                       ],
+                                       2 => [
+                                               1 => TRUE,
+                                               2 => FALSE,
+                                       ],
+                               ]
+                       ],
+                       'TYPO3 Flow Packages' => array(
+                               array( // dependencies
+                                       'TYPO3.Flow' => array(
+                                               'before' => [],
+                                               'after' => array('Symfony.Component.Yaml', 'Doctrine.Common', 'Doctrine.DBAL', 'Doctrine.ORM')
+                                       ),
+                                       'Doctrine.ORM' => array(
+                                               'before' => [],
+                                               'after' => array('Doctrine.Common', 'Doctrine.DBAL')
+                                       ),
+                                       'Doctrine.Common' => array(
+                                               'before' => [],
+                                               'after' => array()
+                                       ),
+                                       'Doctrine.DBAL' => array(
+                                               'before' => [],
+                                               'after' => array('Doctrine.Common')
+                                       ),
+                                       'Symfony.Component.Yaml' => array(
+                                               'before' => [],
+                                               'after' => array()
+                                       ),
+                               ),
+                               array( // graph
+                                       'TYPO3.Flow' => array(
+                                               'TYPO3.Flow' => FALSE,
+                                               'Doctrine.ORM' => TRUE,
+                                               'Doctrine.Common' => TRUE,
+                                               'Doctrine.DBAL' => TRUE,
+                                               'Symfony.Component.Yaml' => TRUE,
+                                       ),
+                                       'Doctrine.ORM' => array(
+                                               'TYPO3.Flow' => FALSE,
+                                               'Doctrine.ORM' => FALSE,
+                                               'Doctrine.Common' => TRUE,
+                                               'Doctrine.DBAL' => TRUE,
+                                               'Symfony.Component.Yaml' => FALSE,
+                                       ),
+                                       'Doctrine.Common' => array(
+                                               'TYPO3.Flow' => FALSE,
+                                               'Doctrine.ORM' => FALSE,
+                                               'Doctrine.Common' => FALSE,
+                                               'Doctrine.DBAL' => FALSE,
+                                               'Symfony.Component.Yaml' => FALSE,
+                                       ),
+                                       'Doctrine.DBAL' => array(
+                                               'TYPO3.Flow' => FALSE,
+                                               'Doctrine.ORM' => FALSE,
+                                               'Doctrine.Common' => TRUE,
+                                               'Doctrine.DBAL' => FALSE,
+                                               'Symfony.Component.Yaml' => FALSE,
+                                       ),
+                                       'Symfony.Component.Yaml' => array(
+                                               'TYPO3.Flow' => FALSE,
+                                               'Doctrine.ORM' => FALSE,
+                                               'Doctrine.Common' => FALSE,
+                                               'Doctrine.DBAL' => FALSE,
+                                               'Symfony.Component.Yaml' => FALSE,
+                                       ),
+                               ),
+                       ),
+                       'TYPO3 CMS Extensions' => array(
+                               array( // dependencies
+                                       'core' => array(
+                                               'before' => [],
+                                               'after' => array(),
+                                       ),
+                                       'openid' => array(
+                                               'before' => [],
+                                               'after' => array('core', 'setup')
+                                       ),
+                                       'scheduler' => array (
+                                               'before' => [],
+                                               'after' => array('core'),
+                                       ),
+                                       'setup' => array (
+                                               'before' => [],
+                                               'after' => array('core'),
+                                       ),
+                                       'sv' => array (
+                                               'before' => [],
+                                               'after' => array('core'),
+                                       ),
+                               ),
+                               array( // graph
+                                       'core' => array(
+                                               'core' => FALSE,
+                                               'setup' => FALSE,
+                                               'sv' => FALSE,
+                                               'scheduler' => FALSE,
+                                               'openid' => FALSE,
+                                       ),
+                                       'openid' => array(
+                                               'core' => TRUE,
+                                               'setup' => TRUE,
+                                               'sv' => FALSE,
+                                               'scheduler' => FALSE,
+                                               'openid' => FALSE,
+                                       ),
+                                       'scheduler' => array (
+                                               'core' => TRUE,
+                                               'setup' => FALSE,
+                                               'sv' => FALSE,
+                                               'scheduler' => FALSE,
+                                               'openid' => FALSE,
+                                       ),
+                                       'setup' => array (
+                                               'core' => TRUE,
+                                               'setup' => FALSE,
+                                               'sv' => FALSE,
+                                               'scheduler' => FALSE,
+                                               'openid' => FALSE,
+                                       ),
+                                       'sv' => array (
+                                               'core' => TRUE,
+                                               'setup' => FALSE,
+                                               'sv' => FALSE,
+                                               'scheduler' => FALSE,
+                                               'openid' => FALSE,
+                                       ),
+                               ),
+                       ),
+                       'Dummy Packages' => array(
+                               array( // dependencies
+                                       'A' => array(
+                                               'before' => [],
+                                               'after' => array('B', 'D', 'C'),
+                                       ),
+                                       'B' => array(
+                                               'before' => [],
+                                               'after' => array()
+                                       ),
+                                       'C' => array(
+                                               'before' => [],
+                                               'after' => array('E')
+                                       ),
+                                       'D' => array (
+                                               'before' => [],
+                                               'after' => array('E'),
+                                       ),
+                                       'E' => array (
+                                               'before' => [],
+                                               'after' => array(),
+                                       ),
+                                       'F' => array (
+                                               'before' => [],
+                                               'after' => array(),
+                                       ),
+                               ),
+                               array( // graph
+                                       'A' => array(
+                                               'A' => FALSE,
+                                               'B' => TRUE,
+                                               'C' => TRUE,
+                                               'D' => TRUE,
+                                               'E' => FALSE,
+                                               'F' => FALSE,
+                                       ),
+                                       'B' => array(
+                                               'A' => FALSE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                               'D' => FALSE,
+                                               'E' => FALSE,
+                                               'F' => FALSE,
+                                       ),
+                                       'C' => array(
+                                               'A' => FALSE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                               'D' => FALSE,
+                                               'E' => TRUE,
+                                               'F' => FALSE,
+                                       ),
+                                       'D' => array (
+                                               'A' => FALSE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                               'D' => FALSE,
+                                               'E' => TRUE,
+                                               'F' => FALSE,
+                                       ),
+                                       'E' => array (
+                                               'A' => FALSE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                               'D' => FALSE,
+                                               'E' => FALSE,
+                                               'F' => FALSE,
+                                       ),
+                                       'F' => array (
+                                               'A' => FALSE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                               'D' => FALSE,
+                                               'E' => FALSE,
+                                               'F' => FALSE,
+                                       ),
+                               ),
+                       ),
+                       'Suggestions without reverse dependency' => array(
+                               array( // dependencies
+                                       'A' => array(
+                                               'before' => [],
+                                               'after' => [],
+                                               'after-resilient' => array('B') // package suggestion
+                                       ),
+                                       'B' => array(
+                                               'before' => [],
+                                               'after' => [],
+                                       ),
+                                       'C' => array(
+                                               'before' => [],
+                                               'after' => array('A')
+                                       ),
+                               ),
+                               array( // graph
+                                       'A' => array(
+                                               'A' => FALSE,
+                                               'B' => TRUE,
+                                               'C' => FALSE,
+                                       ),
+                                       'B' => array(
+                                               'A' => FALSE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                       ),
+                                       'C' => array(
+                                               'A' => TRUE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                       ),
+                               ),
+                       ),
+                       'Suggestions with reverse dependency' => array(
+                               array( // dependencies
+                                       'A' => array(
+                                               'before' => [],
+                                               'after' => [],
+                                               'after-resilient' => array('B'), // package suggestion
+                                       ),
+                                       'B' => array(
+                                               'before' => [],
+                                               'after' => array('A')
+                                       ),
+                                       'C' => array(
+                                               'before' => [],
+                                               'after' => array('A')
+                                       ),
+                               ),
+                               array( // graph
+                                       'A' => array(
+                                               'A' => FALSE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                       ),
+                                       'B' => array(
+                                               'A' => TRUE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                       ),
+                                       'C' => array(
+                                               'A' => TRUE,
+                                               'B' => FALSE,
+                                               'C' => FALSE,
+                                       ),
+                               ),
+                       ),
+               ];
+       }
+
+       /**
+        * @test
+        * @dataProvider calculateOrderResolvesCorrectOrderDataProvider
+        * @param array $graph
+        * @param array $expectedList
+        */
+       public function calculateOrderResolvesCorrectOrder(array $graph, array $expectedList) {
+               $list = (new DependencyOrderingService())->calculateOrder($graph);
+               $this->assertSame($expectedList, $list);
+       }
+
+       /**
+        * @return array
+        */
+       public function calculateOrderResolvesCorrectOrderDataProvider() {
+               return [
+                       'list1' => [
+                               [ // $graph
+                                       1 => [
+                                               1 => FALSE,
+                                               2 => TRUE
+                                       ],
+                                       2 => [
+                                               1 => FALSE,
+                                               2 => FALSE
+                                       ],
+                               ],
+                               [ // $expectedList
+                                       2, 1
+                               ]
+                       ],
+                       'list2' => [
+                               [ // $graph
+                                       1 => [
+                                               1 => FALSE,
+                                               2 => TRUE,
+                                               3 => FALSE,
+                                       ],
+                                       2 => [
+                                               1 => FALSE,
+                                               2 => FALSE,
+                                               3 => FALSE,
+                                       ],
+                                       3 => [
+                                               1 => TRUE,
+                                               2 => TRUE,
+                                               3 => FALSE,
+                                       ],
+                               ],
+                               [ // $expectedList
+                                       2, 1, 3
+                               ]
+                       ],
+               ];
+       }
+
+       /**
+        * @test
+        * @expectedException \UnexpectedValueException
+        * @expectedExceptionCode 1381960494
+        */
+       public function calculateOrderDetectsCyclicGraph() {
+               (new DependencyOrderingService())->calculateOrder([
+                       1 => [
+                               1 => FALSE,
+                               2 => TRUE,
+                       ],
+                       2 => [
+                               1 => TRUE,
+                               2 => FALSE,
+                       ],
+               ]);
+       }
+
+       /**
+        * @return array
+        */
+       public function findPathInGraphReturnsCorrectPathDataProvider() {
+               return array(
+                       'Simple path' => array(
+                               array(
+                                       'A' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => TRUE),
+                                       'B' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE),
+                                       'C' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE),
+                                       'Z' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE)
+                               ),
+                               'A', 'Z',
+                               array('A', 'Z')
+                       ),
+                       'No path' => array(
+                               array(
+                                       'A' => array('A' => FALSE, 'B' => TRUE, 'C' => FALSE, 'Z' => FALSE),
+                                       'B' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE),
+                                       'C' => array('A' => FALSE, 'B' => TRUE, 'C' => FALSE, 'Z' => FALSE),
+                                       'Z' => array('A' => FALSE, 'B' => TRUE, 'C' => FALSE, 'Z' => FALSE)
+                               ),
+                               'A', 'C',
+                               array()
+                       ),
+                       'Longer path' => array(
+                               array(
+                                       'A' => array('A' => FALSE, 'B' => TRUE, 'C' => TRUE, 'Z' => TRUE),
+                                       'B' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE),
+                                       'C' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => TRUE),
+                                       'Z' => array('A' => FALSE, 'B' => FALSE, 'C' => FALSE, 'Z' => FALSE)
+                               ),
+                               'A', 'Z',
+                               array('A', 'C', 'Z')
+                       ),
+               );
+       }
+
+       /**
+        * @param array $graph
+        * @param string $from
+        * @param string $to
+        * @param array $expected
+        * @test
+        * @dataProvider findPathInGraphReturnsCorrectPathDataProvider
+        */
+       public function findPathInGraphReturnsCorrectPath(array $graph, $from, $to, array $expected) {
+               /** @var DependencyOrderingService|\PHPUnit_Framework_MockObject_MockObject|\TYPO3\CMS\Core\Tests\AccessibleObjectInterface $dependencyOrderingService */
+               $dependencyOrderingService = $this->getAccessibleMock(DependencyOrderingService::class, ['dummy']);
+               $path = $dependencyOrderingService->_call('findPathInGraph', $graph, $from, $to);
+
+               $this->assertSame($expected, $path);
+       }
+
+}