9.5/_dependency_ordering_service_8php_source.html

<?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]);


            $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];

            }

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

    }

}