<?php
declare(strict_types=1);

namespace Ekesto\CacheInvalidator\Core\Relationships;

/**
 * Lite-safe relationship cycle detector.
 *
 * Pure graph validation used by settings sanitization. Contains no premium
 * propagation logic, applies no filters, and is required in every build.
 */
final class RelationshipCycleDetector
{
    /**
     * Detect cycles in host -> relationships adjacency.
     *
     * @param array<string,string[]> $adjacencyList
     * @return array{has_cycle:bool,cycle_path:string[]}
     */
    public static function detect(array $adjacencyList): array
    {
        $normalizedAdjacency = [];

        foreach ($adjacencyList as $hostPostType => $relationships) {
            $hostPostType = sanitize_key((string) $hostPostType);
            if ($hostPostType === '') {
                continue;
            }

            $normalizedRelationships = [];
            if (is_array($relationships)) {
                foreach ($relationships as $relatedPostType) {
                    $relatedPostType = sanitize_key((string) $relatedPostType);
                    if ($relatedPostType === '') {
                        continue;
                    }
                    if ($relatedPostType === $hostPostType) {
                        continue;
                    }
                    $normalizedRelationships[] = $relatedPostType;
                }
            }

            $normalizedAdjacency[$hostPostType] = array_values(array_unique($normalizedRelationships));
        }

        // Include relationship-only nodes so DFS sees full node set.
        foreach ($normalizedAdjacency as $relationships) {
            foreach ($relationships as $relatedPostType) {
                if (!isset($normalizedAdjacency[$relatedPostType])) {
                    $normalizedAdjacency[$relatedPostType] = [];
                }
            }
        }

        $state = []; // 0=unvisited, 1=visiting, 2=done
        $stack = [];
        $stackIndex = [];

        $visit = static function (string $node) use (&$visit, &$normalizedAdjacency, &$state, &$stack, &$stackIndex): ?array {
            $state[$node] = 1;
            $stack[] = $node;
            $stackIndex[$node] = count($stack) - 1;

            $neighbors = $normalizedAdjacency[$node] ?? [];
            foreach ($neighbors as $neighbor) {
                $neighborState = (int) ($state[$neighbor] ?? 0);

                if ($neighborState === 1) {
                    $cycleStartIndex = (int) ($stackIndex[$neighbor] ?? 0);
                    $cyclePath = array_slice($stack, $cycleStartIndex);
                    $cyclePath[] = $neighbor;
                    return $cyclePath;
                }

                if ($neighborState === 0) {
                    $cyclePath = $visit($neighbor);
                    if (is_array($cyclePath)) {
                        return $cyclePath;
                    }
                }
            }

            $state[$node] = 2;
            array_pop($stack);
            unset($stackIndex[$node]);

            return null;
        };

        $nodes = array_keys($normalizedAdjacency);
        sort($nodes, SORT_STRING);

        foreach ($nodes as $node) {
            if ((int) ($state[$node] ?? 0) !== 0) {
                continue;
            }

            $cyclePath = $visit($node);
            if (is_array($cyclePath) && !empty($cyclePath)) {
                return [
                    'has_cycle' => true,
                    'cycle_path' => $cyclePath,
                ];
            }
        }

        return [
            'has_cycle' => false,
            'cycle_path' => [],
        ];
    }
}
