<?php
declare(strict_types=1);

namespace PpPhp\Core\Platform\DI\Validation;

use PpPhp\Core\Platform\DI\Graph\DependencyGraph;

final class CircularDependencyDetector
{
    public function detect(DependencyGraph $graph): array
    {
        $cycles = [];
        $visited = [];
        $path = [];

        foreach ($graph->nodes() as $node) {
            $this->visit($node->id(), $graph, $visited, $path, $cycles);
        }

        return $cycles;
    }

    private function visit(string $id, DependencyGraph $graph, array &$visited, array &$path, array &$cycles): void
    {
        if (in_array($id, $path, true)) {
            $start = array_search($id, $path, true);
            $cycles[] = array_values(array_slice([...$path, $id], (int)$start));
            return;
        }

        if (isset($visited[$id])) {
            return;
        }

        $visited[$id] = true;
        $path[] = $id;

        foreach ($graph->dependenciesOf($id) as $dependency) {
            $this->visit($dependency, $graph, $visited, $path, $cycles);
        }

        array_pop($path);
    }
}
