Puli\Manager\Conflict\OverrideGraph

Complexity

Total Complexity

40

Size/Duplication

Total Lines	339
Duplicated Lines	0 %

Coupling/Cohesion

Components	1
Dependencies	4

Test Coverage

Coverage

98.25%

Importance

Changes	2
Bugs	1	Features	1

14 Methods

Rating	Name	Duplication	Size	Complexity
C	forPackages()	0	31	7
A	__construct()	0	4	1
A	addPackageName()	0	12	2
A	addPackageNames()	0	6	2
A	hasPackageName()	0	4	1
B	addEdge()	0	30	4
A	removeEdge()	0	4	1
A	hasEdge()	0	4	1
B	hasPath()	0	21	5
A	getPath()	0	8	2
A	getPackageNames()	0	4	1
B	getSortedPackageNames()	0	27	5
B	getPathDFS()	0	25	5
A	sortPackagesDFS()	0	18	3

<?php

/*
 * This file is part of the puli/manager package.
 *
 * (c) Bernhard Schussek <bschussek@gmail.com>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace Puli\Manager\Conflict;

use Puli\Manager\Api\Package\PackageCollection;
use RuntimeException;

/**
 * A directed, acyclic graph of package names.
 *
 * Packages can be added with {@link addPackageName()}. Edges between these packages
 * can then be added using {@link addEdge()}. Both ends of an edge must have
 * been defined before the edge is added.
 *
 * ```php
 * $graph = new OverrideGraph();
 * $graph->addPackageName('acme/core');
 * $graph->addPackageName('acme/blog');
 * $graph->addPackageName('acme/blog-extension1');
 * $graph->addPackageName('acme/blog-extension2');
 * $graph->addEdge('acme/core', 'acme/blog');
 * $graph->addEdge('acme/blog', 'acme/blog-extension1');
 * $graph->addEdge('acme/blog', 'acme/blog-extension2');
 * $graph->addEdge('acme/blog-extension1', 'acme/blog-extension2');
 * ```
 *
 * You can use {@link getPath()} and {@link hasPath()} to check whether a path
 * exists from one package to the other:
 *
 * ```php
 * // ...
 *
 * $graph->hasPath('acme/blog', 'acme/blog-extension1');
 * // => true
 *
 * $graph->hasPath('acme/blog-extension1', 'acme/blog-extension2');
 * // => false
 *
 * $graph->getPath('acme/core', 'acme/blog-extension2');
 * // => array('acme/core', 'acme/blog', 'acme/blog-extension2')
 * ```
 *
 * With {@link getSortedPackageNames()}, you can sort the packages such that the
 * dependencies defined via the edges are respected:
 *
 * ```php
 * // ...
 *
 * $graph->getSortedPackageNames();
 * // => array('acme/core', 'acme/blog', 'acme/blog-extension1', 'acme/blog-extension2')
 * ```
 *
 * @since  1.0
 *
 * @author Bernhard Schussek <bschussek@gmail.com>
 */
class OverrideGraph
{
    /**
     * Stores the names of all packages (vertices) as keys.
     *
     * @var array
     */
    private $packageNames = array();

    /**
     * Stores the edges in the keys of a multi-dimensional array.
     *
     * The first dimension stores the targets, the second dimension the origins
     * of the edges.
     *
     * @var array
     */
    private $edges = array();

    /**
     * Creates an override graph for the given packages.
     *
     * @param PackageCollection $packages The packages to load.
     *
     * @return static The created override graph.
     */
    public static function forPackages(PackageCollection $packages)
    {
        $graph = new static($packages->getPackageNames());

        foreach ($packages as $package) {
            if (null === $package->getPackageFile()) {
                continue;
            }

            foreach ($package->getPackageFile()->getOverriddenPackages() as $overriddenPackage) {
                if ($graph->hasPackageName($overriddenPackage)) {
                    $graph->addEdge($overriddenPackage, $package->getName());
                }
            }
        }

        // Make sure we have numeric, ascending keys here
        $packageOrder = array_values($packages->getRootPackage()->getPackageFile()->getOverrideOrder());

        // Each package overrides the previous one in the list
        for ($i = 1, $l = count($packageOrder); $i < $l; ++$i) {
            $overriddenPackage = $packageOrder[$i - 1];
            $overridingPackage = $packageOrder[$i];

            if ($graph->hasPackageName($overriddenPackage)) {
                $graph->addEdge($overriddenPackage, $overridingPackage);
            }
        }

        return $graph;
    }

    /**
     * Creates a new graph.
     *
     * @param string[] $packageNames The package names stored in the nodes of
     *                               the graph.
     */
    public function __construct(array $packageNames = array())
    {
        $this->addPackageNames($packageNames);
    }

    /**
     * Adds a package name to the graph.
     *
     * @param string $packageName The package name.
     *
     * @throws RuntimeException If the package name already exists.
     */
    public function addPackageName($packageName)
    {
        if (isset($this->packageNames[$packageName])) {
            throw new RuntimeException(sprintf(
                'The package "%s" was added to the graph twice.',
                $packageName
            ));
        }

        $this->packageNames[$packageName] = true;
        $this->edges[$packageName] = array();
    }

    /**
     * Adds a list of package names to the graph.
     *
     * @param string[] $packageNames The package names.
     *
     * @throws RuntimeException If a package name already exists.
     */
    public function addPackageNames(array $packageNames)
    {
        foreach ($packageNames as $packageName) {
            $this->addPackageName($packageName);
        }
    }

    /**
     * Returns whether a package name exists in the graph.
     *
     * @param string $packageName The package name.
     *
     * @return bool Whether the package name exists.
     */
    public function hasPackageName($packageName)
    {
        return isset($this->packageNames[$packageName]);
    }

    /**
     * Adds a directed edge from one to another package.
     *
     * @param string $from The start package name.
     * @param string $to   The end package name.
     *
     * @throws RuntimeException          If any of the packages does not exist in the
     *                                   graph. Each package must have been added first.
     * @throws CyclicDependencyException If adding the edge would create a cycle.
     */
    public function addEdge($from, $to)
    {
        if (!isset($this->packageNames[$from])) {
            throw new RuntimeException(sprintf(
                'The package "%s" does not exist in the graph.',
                $from
            ));
        }

        if (!isset($this->packageNames[$to])) {
            throw new RuntimeException(sprintf(
                'The package "%s" does not exist in the graph.',
                $to
            ));
        }

        if (null !== ($path = $this->getPath($to, $from))) {
            $last = array_pop($path);

            throw new CyclicDependencyException(sprintf(
                'A cyclic dependency was discovered between the packages "%s" '.
                'and "%s". Please check the "override" keys defined in these'.
                'packages.',
                implode('", "', $path),
                $last
            ));
        }

        $this->edges[$to][$from] = true;
    }

    public function removeEdge($from, $to)
    {
        unset($this->edges[$to][$from]);
    }

    /**
     * Returns whether an edge exists between two packages.
     *
     * @param string $from The start package name.
     * @param string $to   The end package name.
     *
     * @return bool Whether an edge exists from the origin to the target package.
     */
    public function hasEdge($from, $to)
    {
        return isset($this->edges[$to][$from]);
    }

    /**
     * Returns whether a path exists from one to another package.
     *
     * @param string $from The start package name.
     * @param string $to   The end package name.
     *
     * @return bool Whether a path exists from the origin to the target package.
     */
    public function hasPath($from, $to)
    {
        // does not exist in the graph
        if (!isset($this->edges[$to])) {
            return false;
        }

        // adjacent node
        if (isset($this->edges[$to][$from])) {
            return true;
        }

        // DFS
        foreach ($this->edges[$to] as $predecessor => $_) {
            if ($this->hasPath($from, $predecessor)) {
                return true;
            }
        }

        return false;
    }

    /**
     * Returns the path from one to another package.
     *
     * @param string $from The start package name.
     * @param string $to   The end package name.
     *
     * @return string[]|null The path of package names or `null`, if no path

Should the return type not be array|null? Also, consider making the array more specific, something like array<String>, or String[].

     *                       was found.
     */
    public function getPath($from, $to)
    {
        if ($this->getPathDFS($from, $to, $reversePath)) {
            return array_reverse($reversePath);
        }

        return null;
    }

    /**
     * Returns all package names in the graph.
     *
     * @return array All package names in the graph.
     */
    public function getPackageNames()
    {
        return $this->packageNames;
    }

    /**
     * Sorts package names according to the defined edges.
     *
     * The names are sorted such that if two packages p1 and p2 have an edge
     * (p1, p2) in the graph, then p1 comes before p2 in the sorted set.
     *
     * If no package names are passed, all names are sorted.
     *
     * @param string[] $namesToSort The package names which should be sorted.
     *
     * @return string[] The sorted package names.
     *
     * @throws RuntimeException If any of the passed package names does not
     *                          exist in the graph.
     */
    public function getSortedPackageNames(array $namesToSort = array())
    {
        if (count($namesToSort) > 0) {
            $namesToSort = array_flip($namesToSort);

            foreach ($namesToSort as $package => $_) {
                if (!isset($this->packageNames[$package])) {
                    throw new RuntimeException(sprintf(
                        'The package "%s" does not exist in the graph.',
                        $package
                    ));
                }
            }
        } else {
            $namesToSort = $this->packageNames;
        }

        $sorted = array();

        // Do a topologic sort
        // Start with any package and process until no more are left
        while (false !== reset($namesToSort)) {
            $this->sortPackagesDFS(key($namesToSort), $namesToSort, $sorted);
        }

        return $sorted;
    }

    /**
     * Finds a path between packages using Depth-First Search.
     *
     * @param string $from        The start package name.
     * @param string $to          The end package name.
     * @param array  $reversePath The path in reverse order.
     *
     * @return bool Whether a path was found.
     */
    private function getPathDFS($from, $to, &$reversePath = array())

This method is not in camel caps format.

    {
        // does not exist in the graph
        if (!isset($this->edges[$to])) {
            return false;
        }

        $reversePath[] = $to;

        // adjacent node
        if (isset($this->edges[$to][$from])) {
            $reversePath[] = $from;

            return true;
        }

        // DFS
        foreach ($this->edges[$to] as $predecessor => $_) {
            if ($this->getPathDFS($from, $predecessor, $reversePath)) {
                return true;
            }
        }

        return false;
    }

    /**
     * Topologically sorts the given package name into the output array.
     *
     * The resulting array is sorted such that all predecessors of the package
     * come before the package (and their predecessors before them, and so on).
     *
     * @param string $currentName The current package name to sort.
     * @param array  $namesToSort The package names yet to be sorted.
     * @param array  $output      The output array.
     */
    private function sortPackagesDFS($currentName, array &$namesToSort, array &$output)

This method is not in camel caps format.

    {
        unset($namesToSort[$currentName]);

        // Before adding the package itself to the path, add all predecessors.
        // Do so recursively, then we make sure that each package is visited
        // in the path before any of its successors.
        foreach ($this->edges[$currentName] as $predecessor => $_) {
            // The package was already processed. Either the package is on the
            // path already, then we're good. Otherwise, we have a cycle.
            // However, addEdge() guarantees that the graph is cycle-free.
            if (isset($namesToSort[$predecessor])) {
                $this->sortPackagesDFS($predecessor, $namesToSort, $output);
            }
        }

        $output[] = $currentName;
    }
}