DependencyOrderingService.php

Go to the documentation of this file.

<?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!
 */

class DependencyOrderingService
{
    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;
    }

    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)
        $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;
    }

    public function calculateOrder(array $dependencyGraph)
    {
        $rootIds = array_flip($this->findRootIds($dependencyGraph));

        // Add number of dependencies for each root node
        foreach ($rootIds as $id => &$dependencies) {
            $dependencies = count(array_filter($dependencyGraph[$id]));
        }
        unset($dependencies);

        // This will contain our final result in reverse order,
        // meaning a result of [A, B, C] equals "A after B after C"
        $sortedIds = [];

        // Walk through the graph, level by level
        while (!empty($rootIds)) {
            ksort($rootIds);
            // We take those with fewer dependencies first, to have them at the end of the list in the final result.
            $minimum = PHP_INT_MAX;
            $currentId = 0;
            foreach ($rootIds as $id => $count) {
                if ($count <= $minimum) {
                    $minimum = $count;
                    $currentId = $id;
                }
            }
            unset($rootIds[$currentId]);

            array_push($sortedIds, $currentId);

            // Process the dependencies of the current node
            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 to the list
                    $rootIds[$dependingId] = count(array_filter($dependencyGraph[$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);
    }

    protected function getIncomingEdgeCount(array $dependencyGraph, $identifier)
    {
        $incomingEdgeCount = 0;
        foreach ($dependencyGraph as $dependencies) {
            if ($dependencies[$identifier]) {
                $incomingEdgeCount++;
            }
        }
        return $incomingEdgeCount;
    }

    public function findRootIds(array $dependencyGraph)
    {
        // Filter nodes with no incoming edge (aka root nodes)
        $rootIds = [];
        foreach ($dependencyGraph as $id => $_) {
            if (!$this->getIncomingEdgeCount($dependencyGraph, $id)) {
                $rootIds[] = $id;
            }
        }
        return $rootIds;
    }

    protected function findPathInGraph(array $graph, $from, $to)
    {
        foreach (array_filter($graph[$from]) as $node => $_) {
            if ($node === $to) {
                return [$from, $to];
            } else {
                $subPath = $this->findPathInGraph($graph, $node, $to);
                if (!empty($subPath)) {
                    array_unshift($subPath, $from);
                    return $subPath;
                }
            }
        }
        return [];
    }

    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;
    }
}