<?php

namespace Drupal\eb\Service\Dependency;

use Drupal\Core\Entity\EntityTypeManagerInterface;
use Drupal\eb\Exception\ValidationException;
use Drupal\eb\PluginManager\EbExtensionPluginManager;
use Drupal\eb\Service\Traits\EntityKeyTrait;

/**
 * Service for resolving operation dependencies.
 *
 * Builds dependency graph, performs topological sort, and validates
 * dependencies to ensure operations execute in correct order.
 */
class DependencyResolver {

  use EntityKeyTrait;

  /**
   * Constructor.
   *
   * @param \Drupal\Core\Entity\EntityTypeManagerInterface $entityTypeManager
   *   Entity type manager.
   * @param \Drupal\eb\PluginManager\EbExtensionPluginManager $extensionManager
   *   The extension plugin manager.
   */
  public function __construct(
    protected EntityTypeManagerInterface $entityTypeManager,
    protected EbExtensionPluginManager $extensionManager,
  ) {
  }

  /**
   * Resolve dependencies and return sorted operations.
   *
   * @param array<array<string, mixed>> $operations
   *   Array of operation data arrays.
   * @param bool $checkExisting
   *   Whether to check existing Drupal entities.
   *
   * @return array<array<string, mixed>>
   *   Sorted array of operation data arrays.
   *
   * @throws \Drupal\eb\Exception\ValidationException
   *   If circular dependencies or missing dependencies detected.
   */
  public function resolve(array $operations, bool $checkExisting = TRUE): array {
    if (empty($operations)) {
      return [];
    }

    // Build dependency graph.
    $graph = $this->buildGraph($operations);

    // Detect circular dependencies.
    $this->detectCircularDependencies($graph, $operations);

    // Validate dependencies.
    $this->validateDependencies($operations, $graph, $checkExisting);

    // Topological sort.
    return $this->topologicalSort($operations, $graph);
  }

  /**
   * Build dependency graph.
   *
   * @param array<array<string, mixed>> $operations
   *   Array of operation data arrays.
   *
   * @return array<string, array<string>>
   *   Adjacency list representing dependencies.
   */
  protected function buildGraph(array $operations): array {
    $graph = [];

    // Initialize graph nodes.
    foreach ($operations as $index => $operation) {
      $key = $this->makeEntityKey($operation, $index);
      if (!isset($graph[$key])) {
        $graph[$key] = [];
      }
    }

    // Build edges (dependencies).
    foreach ($operations as $index => $operation) {
      $key = $this->makeEntityKey($operation, $index);
      $dependencies = $this->findDependencies($operation, $operations);

      foreach ($dependencies as $depKey) {
        if (!isset($graph[$key])) {
          $graph[$key] = [];
        }
        $graph[$key][] = $depKey;
      }
    }

    return $graph;
  }

  /**
   * Find dependencies for a single operation.
   *
   * @param array<string, mixed> $operation
   *   Operation data.
   * @param array<array<string, mixed>> $allOperations
   *   All operations for reference.
   *
   * @return array<string>
   *   Array of entity keys this operation depends on.
   */
  protected function findDependencies(array $operation, array $allOperations): array {
    $dependencies = [];
    $operationType = $operation['operation'] ?? '';

    // Field operations depend on bundle.
    if (in_array($operationType, ['create_field', 'update_field'])) {
      $entityType = $operation['entity_type'] ?? '';
      $bundle = $operation['bundle'] ?? '';

      if ($entityType && $bundle) {
        $dependencies[] = "bundle:{$entityType}:{$bundle}";
      }

      // Entity reference fields depend on target bundles.
      if (($operation['field_type'] ?? '') === 'entity_reference') {
        $targetBundles = $this->extractTargetBundles($operation);
        foreach ($targetBundles as $targetBundle) {
          $dependencies[] = $targetBundle;
        }
      }
    }

    // Display operations depend on fields.
    if (in_array($operationType, ['configure_form_mode', 'configure_view_mode'])) {
      $entityType = $operation['entity_type'] ?? '';
      $bundle = $operation['bundle'] ?? '';
      $fieldName = $operation['field_name'] ?? '';

      if ($entityType && $bundle && $fieldName) {
        $dependencies[] = "field:{$entityType}:{$bundle}:{$fieldName}";
      }
    }

    // Menu links depend on menu.
    if ($operationType === 'create_menu_link') {
      $menuId = $operation['menu_id'] ?? '';
      if ($menuId) {
        $dependencies[] = "menu:{$menuId}";
      }

      // Nested menu links depend on parent.
      if (isset($operation['parent'])) {
        $dependencies[] = "menu_link:{$menuId}:{$operation['parent']}";
      }
    }

    // Allow extension plugins to add operation dependencies.
    $context = ['all_operations' => $allOperations];
    foreach ($this->extensionManager->getExtensions() as $extension) {
      if ($extension->appliesTo($operation)) {
        $extensionDeps = $extension->getOperationDependencies($operation, $context);
        $dependencies = array_merge($dependencies, $extensionDeps);
      }
    }

    return array_unique($dependencies);
  }

  /**
   * Extract target bundles from entity reference field.
   *
   * @param array<string, mixed> $operation
   *   Field operation data.
   *
   * @return array<string>
   *   Array of bundle keys (e.g., "bundle:taxonomy_term:tags").
   */
  protected function extractTargetBundles(array $operation): array {
    $targetBundles = [];

    $targetType = $operation['field_storage_settings']['target_type'] ?? NULL;
    if (!$targetType) {
      return $targetBundles;
    }

    $handlerSettings = $operation['field_config_settings']['handler_settings'] ?? [];
    $targetBundleIds = $handlerSettings['target_bundles'] ?? [];

    foreach ($targetBundleIds as $bundleId) {
      $targetBundles[] = "bundle:{$targetType}:{$bundleId}";
    }

    return $targetBundles;
  }

  /**
   * Detect circular dependencies using DFS.
   *
   * @param array<string, array<string>> $graph
   *   Dependency graph.
   * @param array<array<string, mixed>> $operations
   *   Operations for error messages.
   *
   * @throws \Drupal\eb\Exception\ValidationException
   *   If circular dependency detected.
   */
  protected function detectCircularDependencies(array $graph, array $operations): void {
    $visited = [];
    $recursionStack = [];

    foreach (array_keys($graph) as $node) {
      if (!isset($visited[$node])) {
        $cycle = $this->dfsDetectCycle($node, $graph, $visited, $recursionStack, []);
        if (!empty($cycle)) {
          $this->throwCircularDependencyError($cycle);
        }
      }
    }
  }

  /**
   * DFS to detect cycles in graph.
   *
   * @param string $node
   *   Current node.
   * @param array<string, array<string>> $graph
   *   Dependency graph.
   * @param array<string, bool> $visited
   *   Visited nodes.
   * @param array<string, bool> $recursionStack
   *   Current recursion stack.
   * @param array<string> $path
   *   Current path for cycle detection.
   *
   * @return array<string>
   *   Cycle path if found, empty array otherwise.
   */
  protected function dfsDetectCycle(string $node, array $graph, array &$visited, array &$recursionStack, array $path): array {
    $visited[$node] = TRUE;
    $recursionStack[$node] = TRUE;
    $path[] = $node;

    $dependencies = $graph[$node] ?? [];
    foreach ($dependencies as $dependency) {
      if (!isset($visited[$dependency])) {
        $cycle = $this->dfsDetectCycle($dependency, $graph, $visited, $recursionStack, $path);
        if (!empty($cycle)) {
          return $cycle;
        }
      }
      elseif (isset($recursionStack[$dependency]) && $recursionStack[$dependency]) {
        // Found cycle - return path from dependency to current node.
        $cycleStart = array_search($dependency, $path);
        return array_slice($path, $cycleStart);
      }
    }

    $recursionStack[$node] = FALSE;
    return [];
  }

  /**
   * Throw circular dependency error with helpful message.
   *
   * @param array<string> $cycle
   *   Cycle path.
   *
   * @throws \Drupal\eb\Exception\ValidationException
   *   Circular dependency error.
   */
  protected function throwCircularDependencyError(array $cycle): void {
    $cycleStr = implode(' → ', $cycle) . ' → ' . reset($cycle);

    $message = "Circular dependency detected: {$cycleStr}\n\n";
    $message .= "Suggestion: Create bundles first, then add cross-reference fields in separate operations.";

    throw new ValidationException($message);
  }

  /**
   * Validate all dependencies are satisfied.
   *
   * @param array<array<string, mixed>> $operations
   *   Operations.
   * @param array<string, array<string>> $graph
   *   Dependency graph.
   * @param bool $checkExisting
   *   Whether to check existing Drupal entities.
   *
   * @throws \Drupal\eb\Exception\ValidationException
   *   If missing dependencies found.
   */
  protected function validateDependencies(array $operations, array $graph, bool $checkExisting): void {
    // Build set of provided entities.
    $provided = array_keys($graph);

    // Collect all dependencies that need to be checked.
    $toCheck = [];
    foreach ($graph as $dependencies) {
      foreach ($dependencies as $dependency) {
        // Skip if dependency is provided in YAML.
        if (in_array($dependency, $provided)) {
          continue;
        }
        $toCheck[$dependency] = $dependency;
      }
    }

    // Check dependencies in batches for better performance.
    $missing = [];
    if ($checkExisting && !empty($toCheck)) {
      $existingEntities = $this->batchCheckEntities(array_keys($toCheck));
      foreach ($toCheck as $dependency) {
        if (!isset($existingEntities[$dependency]) || !$existingEntities[$dependency]) {
          $missing[$dependency] = $dependency;
        }
      }
    }
    elseif (!$checkExisting) {
      // If not checking existing, all unprovided dependencies are missing.
      $missing = $toCheck;
    }

    if (!empty($missing)) {
      $this->throwMissingDependencyError($missing);
    }
  }

  /**
   * Batch check if multiple entities exist in Drupal.
   *
   * Groups entity keys by type and performs batch queries to minimize
   * database round trips. Performance: O(t) queries where t = number of
   * entity types, instead of O(n) queries where n = number of dependencies.
   *
   * @param array<string> $entityKeys
   *   Entity keys (e.g., ["bundle:node:article", "field:..."]).
   *
   * @return array<string, bool>
   *   Keyed array of entity key => exists (bool).
   */
  protected function batchCheckEntities(array $entityKeys): array {
    $results = [];
    $grouped = $this->groupDependenciesByType($entityKeys);

    // Check bundles in batch.
    if (!empty($grouped['bundle'])) {
      $results += $this->batchCheckBundles($grouped['bundle']);
    }

    // Check fields in batch.
    if (!empty($grouped['field'])) {
      $results += $this->batchCheckFields($grouped['field']);
    }

    // Check menus in batch.
    if (!empty($grouped['menu'])) {
      $results += $this->batchCheckMenus($grouped['menu']);
    }

    // Check roles in batch.
    if (!empty($grouped['role'])) {
      $results += $this->batchCheckRoles($grouped['role']);
    }

    // Collect unchecked keys for extension plugins to handle.
    $uncheckedKeys = [];
    foreach ($entityKeys as $key) {
      if (!isset($results[$key])) {
        $uncheckedKeys[] = $key;
      }
    }

    // Allow extension plugins to check their custom dependency types.
    // This enables plugins like FieldGroupExtension to verify dependencies.
    if (!empty($uncheckedKeys)) {
      foreach ($this->extensionManager->getExtensions() as $extension) {
        $extensionResults = $extension->checkDependencies($uncheckedKeys);
        foreach ($extensionResults as $key => $exists) {
          if (in_array($key, $uncheckedKeys, TRUE)) {
            $results[$key] = (bool) $exists;
          }
        }
      }
    }

    // Mark any still-unchecked keys as not existing.
    foreach ($entityKeys as $key) {
      if (!isset($results[$key])) {
        $results[$key] = FALSE;
      }
    }

    return $results;
  }

  /**
   * Group entity keys by their type for batch processing.
   *
   * @param array<string> $entityKeys
   *   Entity keys to group.
   *
   * @return array<string, mixed>
   *   Grouped keys structure varies by type.
   */
  protected function groupDependenciesByType(array $entityKeys): array {
    $grouped = [
      'bundle' => [],
      'field' => [],
      'menu' => [],
      'role' => [],
    ];

    foreach ($entityKeys as $key) {
      $parts = explode(':', $key);
      $type = $parts[0];

      switch ($type) {
        case 'bundle':
          $entityType = $parts[1] ?? '';
          $bundleId = $parts[2] ?? '';
          if ($entityType && $bundleId) {
            $grouped['bundle'][$entityType][$bundleId] = $key;
          }
          break;

        case 'field':
          $entityType = $parts[1] ?? '';
          $bundle = $parts[2] ?? '';
          $fieldName = $parts[3] ?? '';
          if ($entityType && $bundle && $fieldName) {
            $fieldId = "{$entityType}.{$bundle}.{$fieldName}";
            $grouped['field'][$fieldId] = $key;
          }
          break;

        case 'menu':
          $menuId = $parts[1] ?? '';
          if ($menuId) {
            $grouped['menu'][$menuId] = $key;
          }
          break;

        case 'role':
          $roleId = $parts[1] ?? '';
          if ($roleId) {
            $grouped['role'][$roleId] = $key;
          }
          break;
      }
    }

    return $grouped;
  }

  /**
   * Batch check bundles existence.
   *
   * @param array<string, array<string, string>> $bundles
   *   Bundles grouped by entity type: ['node' => ['article' => 'bundle:...']].
   *
   * @return array<string, bool>
   *   Results keyed by original entity key.
   */
  protected function batchCheckBundles(array $bundles): array {
    $results = [];

    foreach ($bundles as $entityType => $bundleMapping) {
      try {
        $bundleEntityType = $this->entityTypeManager
          ->getDefinition($entityType)
          ->getBundleEntityType();

        if (!$bundleEntityType) {
          // No bundle entity type (e.g., user) - check if bundle matches.
          foreach ($bundleMapping as $bundleId => $originalKey) {
            $results[$originalKey] = ($bundleId === $entityType);
          }
          continue;
        }

        // Batch load all bundles for this entity type.
        $bundleIds = array_keys($bundleMapping);
        $storage = $this->entityTypeManager->getStorage($bundleEntityType);
        $loadedBundles = $storage->loadMultiple($bundleIds);

        foreach ($bundleMapping as $bundleId => $originalKey) {
          $results[$originalKey] = isset($loadedBundles[$bundleId]);
        }
      }
      catch (\Exception $e) {
        // If entity type doesn't exist, mark all bundles as not existing.
        foreach ($bundleMapping as $originalKey) {
          $results[$originalKey] = FALSE;
        }
      }
    }

    return $results;
  }

  /**
   * Batch check fields existence.
   *
   * @param array<string, string>|array<string, array<string>> $fields
   *   Fields keyed by field config ID.
   *
   * @return array<string, bool>
   *   Results keyed by original entity key.
   */
  protected function batchCheckFields(array $fields): array {
    $results = [];

    if (empty($fields)) {
      return $results;
    }

    try {
      $fieldIds = array_keys($fields);
      $storage = $this->entityTypeManager->getStorage('field_config');
      $loadedFields = $storage->loadMultiple($fieldIds);

      foreach ($fields as $fieldId => $originalKey) {
        $results[$originalKey] = isset($loadedFields[$fieldId]);
      }
    }
    catch (\Exception $e) {
      // Mark all fields as not existing on error.
      foreach ($fields as $originalKey) {
        $results[$originalKey] = FALSE;
      }
    }

    return $results;
  }

  /**
   * Batch check menus existence.
   *
   * @param array<string, string>|array<string, array<string>> $menus
   *   Menus keyed by menu ID.
   *
   * @return array<string, bool>
   *   Results keyed by original entity key.
   */
  protected function batchCheckMenus(array $menus): array {
    $results = [];

    if (empty($menus)) {
      return $results;
    }

    try {
      $menuIds = array_keys($menus);
      $storage = $this->entityTypeManager->getStorage('menu');
      $loadedMenus = $storage->loadMultiple($menuIds);

      foreach ($menus as $menuId => $originalKey) {
        $results[$originalKey] = isset($loadedMenus[$menuId]);
      }
    }
    catch (\Exception $e) {
      // Mark all menus as not existing on error.
      foreach ($menus as $originalKey) {
        $results[$originalKey] = FALSE;
      }
    }

    return $results;
  }

  /**
   * Batch check roles existence.
   *
   * @param array<string, string>|array<string, array<string>> $roles
   *   Roles keyed by role ID.
   *
   * @return array<string, bool>
   *   Results keyed by original entity key.
   */
  protected function batchCheckRoles(array $roles): array {
    $results = [];

    if (empty($roles)) {
      return $results;
    }

    try {
      $roleIds = array_keys($roles);
      $storage = $this->entityTypeManager->getStorage('user_role');
      $loadedRoles = $storage->loadMultiple($roleIds);

      foreach ($roles as $roleId => $originalKey) {
        $results[$originalKey] = isset($loadedRoles[$roleId]);
      }
    }
    catch (\Exception $e) {
      // Mark all roles as not existing on error.
      foreach ($roles as $originalKey) {
        $results[$originalKey] = FALSE;
      }
    }

    return $results;
  }

  /**
   * Check if entity exists in Drupal.
   *
   * @param string $entityKey
   *   Entity key (e.g., "bundle:node:article").
   *
   * @return bool
   *   TRUE if entity exists.
   */
  protected function entityExistsInDrupal(string $entityKey): bool {
    $results = $this->batchCheckEntities([$entityKey]);
    return $results[$entityKey] ?? FALSE;
  }

  /**
   * Throw missing dependency error.
   *
   * @param array<string> $missing
   *   Missing dependencies.
   *
   * @throws \Drupal\eb\Exception\ValidationException
   *   Missing dependency error.
   */
  protected function throwMissingDependencyError(array $missing): void {
    $message = "Missing dependencies:\n\n";

    foreach ($missing as $dep) {
      $message .= "  - {$dep} is not defined in YAML or Drupal\n";
    }

    $message .= "\nSuggestion: Add the missing entity definitions or ensure they exist in Drupal.";

    throw new ValidationException($message);
  }

  /**
   * Topological sort of operations using Kahn's algorithm.
   *
   * @param array<array<string, mixed>> $operations
   *   Operations.
   * @param array<string, array<string>> $graph
   *   Dependency graph.
   *
   * @return array<array<string, mixed>>
   *   Sorted operations.
   */
  protected function topologicalSort(array $operations, array $graph): array {
    // Build index of operations by key.
    $operationsByKey = [];
    foreach ($operations as $index => $operation) {
      $key = $this->makeEntityKey($operation, $index);
      $operationsByKey[$key] = $operation;
    }

    // Calculate in-degree for each node.
    // In-degree = number of dependencies this node has.
    $inDegree = [];
    foreach ($graph as $node => $dependencies) {
      $inDegree[$node] = count($dependencies);
    }

    // Add all nodes with in-degree 0 to queue.
    $queue = [];
    foreach ($inDegree as $node => $degree) {
      if ($degree === 0) {
        $queue[] = $node;
      }
    }

    // Process queue.
    $sorted = [];
    while (!empty($queue)) {
      $node = array_shift($queue);
      $sorted[] = $node;

      // For each node that depends on current node.
      foreach (array_keys($graph) as $otherNode) {
        if (in_array($node, $graph[$otherNode])) {
          $inDegree[$otherNode]--;
          if ($inDegree[$otherNode] === 0) {
            $queue[] = $otherNode;
          }
        }
      }
    }

    // Convert sorted keys back to operations.
    $sortedOperations = [];
    foreach ($sorted as $key) {
      if (isset($operationsByKey[$key])) {
        $sortedOperations[] = $operationsByKey[$key];
      }
    }

    return $sortedOperations;
  }

  /**
   * Generate entity key for graph nodes.
   *
   * @param array<string, mixed> $operation
   *   Operation data.
   * @param int $index
   *   Operation index (for uniqueness).
   *
   * @return string
   *   Key like "bundle:node:article" or "field:node:article:field_test".
   */
  protected function makeEntityKey(array $operation, int $index): string {
    $operationType = $operation['operation'] ?? '';

    if (in_array($operationType, ['create_bundle', 'update_bundle'])) {
      $entityType = $operation['entity_type'] ?? '';
      $bundleId = $operation['bundle_id'] ?? '';
      return "bundle:{$entityType}:{$bundleId}";
    }

    if (in_array($operationType, ['create_field', 'update_field'])) {
      $entityType = $operation['entity_type'] ?? '';
      $bundle = $operation['bundle'] ?? '';
      $fieldName = $operation['field_name'] ?? '';
      return "field:{$entityType}:{$bundle}:{$fieldName}";
    }

    if (in_array($operationType, ['configure_form_mode', 'configure_view_mode'])) {
      $entityType = $operation['entity_type'] ?? '';
      $bundle = $operation['bundle'] ?? '';
      $displayMode = $operation['display_mode'] ?? 'default';
      $fieldName = $operation['field_name'] ?? '';
      $displayType = $operationType === 'configure_form_mode' ? 'form' : 'view';
      return "display:{$displayType}:{$entityType}:{$bundle}:{$displayMode}:{$fieldName}";
    }

    if ($operationType === 'create_menu') {
      $menuId = $operation['menu_id'] ?? '';
      return "menu:{$menuId}";
    }

    if ($operationType === 'create_menu_link') {
      $menuId = $operation['menu_id'] ?? '';
      $title = $operation['title'] ?? '';
      return "menu_link:{$menuId}:{$title}";
    }

    // Fallback for unknown operation types.
    return "operation:{$operationType}:{$index}";
  }

}
