<?php
/**
 * Copyright © Magento, Inc. All rights reserved.
 * See COPYING.txt for license details.
 */
namespace Magento\Setup\Module\Dependency;

use Magento\Framework\Data\Graph;

/**
 * Build circular dependencies by modules map
 */
class Circular
{
    /**
     * Map where the key is the vertex and the value are the adjacent vertices(dependencies) of this vertex
     *
     * @var array
     */
    protected $dependencies = [];

    /**
     * Modules circular dependencies map
     *
     * @var array
     */
    protected $circularDependencies = [];

    /**
     * Graph object
     *
     * @var \Magento\Framework\Data\Graph
     */
    protected $graph;

    /**
     * Build modules dependencies
     *
     * @param array $dependencies Key is the vertex and the value are the adjacent vertices(dependencies) of this vertex
     * @return array
     */
    public function buildCircularDependencies($dependencies)
    {
        $this->init($dependencies);

        foreach (array_keys($this->dependencies) as $vertex) {
            $this->expandDependencies($vertex);
        }

        $circulars = $this->graph->findCycle(null, false);
        foreach ($circulars as $circular) {
            array_shift($circular);
            $this->buildCircular($circular);
        }

        return $this->divideByModules($this->circularDependencies);
    }

    /**
     * Init data before building
     *
     * @param array $dependencies
     * @return void
     */
    protected function init($dependencies)
    {
        $this->dependencies = $dependencies;
        $this->circularDependencies = [];
        $this->graph = new Graph(array_keys($this->dependencies), []);
    }

    /**
     * Expand modules dependencies from chain
     *
     * @param string $vertex
     * @param array $path nesting path
     * @return void
     */
    protected function expandDependencies($vertex, $path = [])
    {
        if (!$this->dependencies[$vertex]) {
            return;
        }

        $path[] = $vertex;
        foreach ($this->dependencies[$vertex] as $dependency) {
            if (!isset($this->dependencies[$dependency])) {
                // dependency vertex is not described in basic definition
                continue;
            }
            $relations = $this->graph->getRelations();
            if (isset($relations[$vertex][$dependency])) {
                continue;
            }
            $this->graph->addRelation($vertex, $dependency);

            $searchResult = array_search($dependency, $path);

            if (false !== $searchResult) {
                $this->buildCircular(array_slice($path, $searchResult));
                break;
            } else {
                $this->expandDependencies($dependency, $path);
            }
        }
    }

    /**
     * Build all circular dependencies based on chain
     *
     * @param array $modules
     * @return void
     */
    protected function buildCircular($modules)
    {
        $path = '/' . implode('/', $modules);
        if (isset($this->circularDependencies[$path])) {
            return;
        }
        $this->circularDependencies[$path] = $modules;
        $modules[] = array_shift($modules);
        $this->buildCircular($modules);
    }

    /**
     * Divide dependencies by modules
     *
     * @param array $circularDependencies
     * @return array
     */
    protected function divideByModules($circularDependencies)
    {
        $dependenciesByModule = [];
        foreach ($circularDependencies as $circularDependency) {
            $module = $circularDependency[0];
            $circularDependency[] = $module;
            $dependenciesByModule[$module][] = $circularDependency;
        }

        return $dependenciesByModule;
    }
}