/**
 * Module dependency graph.
 *
 * Builds a directed graph from a set of module manifests where an edge
 * `consumer → provider` exists iff the consumer's `requires` or
 * `optional` capabilities list a name that the provider declares in
 * `provides`. The graph is used by both `system audit` (to render the
 * dependency tree) and `system update` (to walk in topological order
 * so providers upgrade before consumers).
 *
 * Pure data structures and pure operations — no I/O, no logging.
 * Used by tests directly.
 */

import type { ModuleManifest } from '../../manifest/schema';

/**
 * The id used to identify a module in the graph. Always equals
 * `manifest.id` so callers don't need a separate keyspace.
 */
export type ModuleId = string;

export interface ModuleNode {
  id: ModuleId;
  manifest: ModuleManifest;
  /**
   * Capability names this module provides (the keys in
   * `manifest.provides.capabilities[].name`). Cached for graph
   * construction.
   */
  provides: string[];
  /**
   * Required + optional capability names. Optional reqs participate
   * in the graph the same way required ones do — they shape the
   * upgrade order — but they don't block deploy if absent.
   */
  consumes: string[];
}

export interface ModuleGraph {
  nodes: Map<ModuleId, ModuleNode>;
  /** consumer → providers it depends on */
  edges: Map<ModuleId, Set<ModuleId>>;
  /** provider → consumers that depend on it (reverse index) */
  reverseEdges: Map<ModuleId, Set<ModuleId>>;
}

/**
 * Internal: index capability name → EVERY module providing it.
 *
 * This used to keep only the first provider, on the reasoning that "one edge per
 * capability is enough for graph-walking". It is not, and the discrepancy is
 * not theoretical: `firewall` is provided by BOTH `iptables` and `greenwave`,
 * and `capability-loader.ts` resolves a consumer's `requires: firewall` through
 * `buildFirewallChain()`, which wires a chain across ALL providers — the edge
 * device that owns egress plus the downstream layers. So a consumer genuinely
 * depends on every one of them.
 *
 * With first-wins, whichever provider happened to be inserted first absorbed the
 * edge and the others became invisible to the graph. `module pause --cascade
 * greenwave` therefore omitted `caddy` entirely, even though caddy requires
 * `firewall` and greenwave provides it — so the operator paused an incomplete
 * set and `module remove` then refused, because the remove guard reads the
 * capabilities table (all providers) and disagreed. That disagreement is exactly
 * what openspec/changes/module-pause-lifecycle design D3 forbids.
 *
 * Keeping all providers makes the graph agree with how capabilities actually
 * resolve. For `topologicalOrder` it means a consumer sorts after every provider
 * of what it consumes, which is strictly more correct for `system update`.
 */
function indexProviders(modules: ModuleNode[]): Map<string, ModuleId[]> {
  const index = new Map<string, ModuleId[]>();
  for (const m of modules) {
    for (const cap of m.provides) {
      const existing = index.get(cap);
      if (existing) existing.push(m.id);
      else index.set(cap, [m.id]);
    }
  }
  return index;
}

export function buildModuleGraph(manifests: ModuleManifest[]): ModuleGraph {
  const nodes = new Map<ModuleId, ModuleNode>();
  for (const m of manifests) {
    const provides = (m.provides?.capabilities ?? []).map((c) => c.name);
    const required = (m.requires?.capabilities ?? []).map((c) => c.name);
    const optional = (m.optional?.capabilities ?? []).map((c) => c.name);
    nodes.set(m.id, {
      id: m.id,
      manifest: m,
      provides,
      consumes: [...required, ...optional],
    });
  }

  const providerIndex = indexProviders([...nodes.values()]);
  const edges = new Map<ModuleId, Set<ModuleId>>();
  const reverseEdges = new Map<ModuleId, Set<ModuleId>>();

  for (const node of nodes.values()) {
    edges.set(node.id, new Set());
    reverseEdges.set(node.id, reverseEdges.get(node.id) ?? new Set());

    for (const cap of node.consumes) {
      for (const providerId of providerIndex.get(cap) ?? []) {
        // Skip self-edges (a module that consumes its own capability —
        // unusual but legal) and missing providers (deploy preflight
        // handles those; graph just routes around them).
        if (providerId === node.id) continue;

        edges.get(node.id)?.add(providerId);
        const rev = reverseEdges.get(providerId) ?? new Set();
        rev.add(node.id);
        reverseEdges.set(providerId, rev);
      }
    }
  }

  return { nodes, edges, reverseEdges };
}

export class DependencyCycleError extends Error {
  readonly cycle: readonly ModuleId[];
  constructor(cycle: readonly ModuleId[]) {
    super(`Dependency cycle detected: ${cycle.join(' → ')} → ${cycle[0]}`);
    this.name = 'DependencyCycleError';
    this.cycle = cycle;
  }
}

/**
 * Return module ids in dependency-safe order: every provider precedes
 * every consumer. Throws `DependencyCycleError` if the graph contains
 * a cycle (manifest declares mutual dependency, which is a bug in
 * the manifests).
 *
 * Tie-breaks alphabetically so the order is deterministic across runs.
 */
export function topologicalOrder(graph: ModuleGraph): ModuleId[] {
  const order: ModuleId[] = [];
  const visited = new Set<ModuleId>();
  const visiting = new Set<ModuleId>();

  function visit(id: ModuleId, path: ModuleId[]): void {
    if (visited.has(id)) return;
    if (visiting.has(id)) {
      const cycleStart = path.indexOf(id);
      throw new DependencyCycleError(path.slice(cycleStart));
    }
    visiting.add(id);

    // Visit providers first (deterministic order).
    const providers = [...(graph.edges.get(id) ?? [])].sort();
    for (const dep of providers) {
      visit(dep, [...path, id]);
    }

    visiting.delete(id);
    visited.add(id);
    order.push(id);
  }

  // Iterate in alphabetical order so callers without explicit deps
  // get a stable order.
  const ids = [...graph.nodes.keys()].sort();
  for (const id of ids) {
    visit(id, []);
  }

  return order;
}

/**
 * Return all consumers (transitively) of `moduleId`. Used during update
 * to find the subtree that should be skipped when a provider's upgrade
 * fails (subject to the version-aware short-circuit in D3).
 */
export function transitiveConsumers(graph: ModuleGraph, moduleId: ModuleId): ModuleId[] {
  const result: ModuleId[] = [];
  const seen = new Set<ModuleId>([moduleId]);
  const stack = [...(graph.reverseEdges.get(moduleId) ?? [])];

  while (stack.length > 0) {
    const next = stack.pop();
    if (next === undefined || seen.has(next)) continue;
    seen.add(next);
    result.push(next);
    const consumers = graph.reverseEdges.get(next);
    if (consumers) stack.push(...consumers);
  }

  return result.sort();
}

/**
 * Group nodes into "levels" where level 0 has no dependencies inside
 * the graph, level 1 depends only on level 0, etc. Useful for
 * rendering the audit / dry-run output as an indented tree.
 */
export function levelsOf(graph: ModuleGraph): ModuleId[][] {
  const levelByModule = new Map<ModuleId, number>();

  function levelOf(id: ModuleId, path: Set<ModuleId>): number {
    const cached = levelByModule.get(id);
    if (cached !== undefined) return cached;
    if (path.has(id)) {
      // Cycle — return 0 so the topological-order check surfaces a clearer error.
      return 0;
    }
    const deps = graph.edges.get(id);
    if (!deps || deps.size === 0) {
      levelByModule.set(id, 0);
      return 0;
    }
    const next = new Set(path);
    next.add(id);
    let max = 0;
    for (const d of deps) {
      max = Math.max(max, levelOf(d, next) + 1);
    }
    levelByModule.set(id, max);
    return max;
  }

  for (const id of graph.nodes.keys()) {
    levelOf(id, new Set());
  }

  const levels: ModuleId[][] = [];
  for (const [id, lvl] of levelByModule) {
    while (levels.length <= lvl) levels.push([]);
    levels[lvl].push(id);
  }
  for (const lvl of levels) lvl.sort();
  return levels;
}