/**
 * The bounded capability closure: which modules a selected module stands on.
 *
 * Pure, so the console's central question is answerable without a database and
 * the awkward graph shapes below are testable directly.
 *
 * The edge is `planConsumerCleanup()`'s edge, called rather than copied. That
 * function already answers "which providers does this module reach", already
 * counts `requires` AND `optional` as dependency edges, and already handles the
 * two cases a fresh implementation gets wrong: a capability with several
 * providers (firewall has an edge provider plus inner layers, all of them real)
 * and a module that both provides and consumes a capability, which must not
 * become its own dependency. A second walk would drift from it.
 *
 * What this adds is the part a one-hop cleanup plan has no use for: distance,
 * optionality, and termination.
 */

import {
  type ConsumedCapabilities,
  type ProviderRow,
  type ProviderState,
  planConsumerCleanup,
} from '../services/consumer-cleanup';

/**
 * Hops to walk when the caller does not say.
 *
 * Two, because the fleet's useful answer is "what this stands on, and what that
 * stands on". Deliberately a default and not a law: `depth: UNBOUNDED` walks the
 * whole graph, and the walk terminates on cycles either way.
 */
export const DEFAULT_CLOSURE_DEPTH = 2;

/** Walk until the graph runs out rather than until a hop count does. */
export const UNBOUNDED_CLOSURE_DEPTH = 0;

export interface ClosureRequest {
  rootModuleId: string;
  /**
   * Each module's consumed capabilities, by module id. A module with no entry
   * ends that branch of the walk rather than failing the whole thing: a manifest
   * celilo cannot parse is a real state, and one bad row must not blank the
   * picture.
   */
  manifests: ReadonlyMap<string, ConsumedCapabilities>;
  providerRows: readonly ProviderRow[];
  providerStates: readonly ProviderState[];
  depth?: number;
  /**
   * Which providers each module has actually called into, keyed by module id
   * then capability name.
   *
   * When supplied, the walk follows only real bindings. Without it the walk
   * follows every declared capability, which answers "what could this reach"
   * rather than "what is this standing on". Optional so the walk stays testable
   * without a database, not so the distinction is optional.
   */
  bindings?: ReadonlyMap<string, ReadonlyMap<string, string>>;
  /**
   * Ordered provider chains, most downstream first.
   *
   * These are edges NO MANIFEST DECLARES. celilo wires the `firewall`
   * providers into a chain at hook time from `has_external`, so `iptables`
   * genuinely stands on `axon` while neither manifest says a word about the
   * other. A walk over manifests alone stops at `iptables`, and the box the
   * packet actually leaves through never appears in the answer.
   *
   * Supplied by the caller rather than derived here so this stays pure. The CLI
   * reads them with `loadFirewallChain`.
   */
  chains?: readonly DelegationChain[];
}

/**
 * One capability's providers in delegation order.
 *
 * Ordered because for `firewall` they are not alternatives: the order is the
 * packet's path. Same shape as the console protocol's `DelegationChain`, so the
 * server hands it on rather than translating it.
 */
export interface DelegationChain {
  capability: string;
  /** Module ids, most downstream first. */
  moduleIds: string[];
}

export interface ClosureNode {
  moduleId: string;
  /** 1 is a direct dependency of the root. */
  hop: number;
  /**
   * True when every edge that reaches this module is an `optional.capabilities`
   * edge.
   *
   * Load-bearing rather than cosmetic: on a real fleet the internal DNS resolver
   * is reached only optionally, so a walk that followed `requires` alone drops
   * the resolver out of the picture entirely while looking complete.
   */
  optional: boolean;
  /** Capability names by which the walk reached this module, sorted. */
  via: string[];
}

export interface ClosureResult {
  nodes: ClosureNode[];
  /**
   * The delegation chains this closure touched, whole.
   *
   * A chain is emitted when the walk reached ANY of its members, and it carries
   * every member rather than only the reached ones, because half a path is not
   * a path. Empty means the closure touched no chain — which, now that
   * something computes them, is an answer rather than a gap.
   */
  chains: DelegationChain[];
  /** Hops actually walked. Echoes the request so the console can say what it bounded. */
  depth: number;
  /**
   * True when the walk stopped because it hit the bound and the graph continued.
   * Distinct from an exhausted graph, which is a complete answer.
   */
  truncated: boolean;
}

interface Edge {
  to: string;
  hop: number;
  capability: string;
  optional: boolean;
}

/**
 * Which of a module's consumed capabilities it declared as optional.
 *
 * A name in both sets counts as required: `requires` is the stronger claim, and
 * a module that declares a capability both ways still fails without it.
 */
function optionalCapabilityNames(manifest: ConsumedCapabilities): Set<string> {
  const required = new Set((manifest.requires?.capabilities ?? []).map((c) => c.name));
  return new Set(
    (manifest.optional?.capabilities ?? []).map((c) => c.name).filter((n) => !required.has(n)),
  );
}

/**
 * A chain's consecutive pairs, as edges out of each member.
 *
 * `[iptables, axon]` becomes one edge `iptables -> axon`. The last member has
 * no edge out of it: it is the internet-facing end and delegates to nothing.
 */
function delegationEdgesByModule(
  chains: readonly DelegationChain[],
): Map<string, { to: string; capability: string }[]> {
  const byModule = new Map<string, { to: string; capability: string }[]>();
  for (const chain of chains) {
    for (let i = 0; i + 1 < chain.moduleIds.length; i += 1) {
      const from = chain.moduleIds[i];
      const to = chain.moduleIds[i + 1];
      if (from === undefined || to === undefined) continue;
      const out = byModule.get(from) ?? [];
      out.push({ to, capability: chain.capability });
      byModule.set(from, out);
    }
  }
  return byModule;
}

export function computeClosure(request: ClosureRequest): ClosureResult {
  const depth = request.depth ?? DEFAULT_CLOSURE_DEPTH;
  const providerRows = [...request.providerRows];
  const providerStates = [...request.providerStates];
  const chains = request.chains ?? [];
  const delegationsOut = delegationEdgesByModule(chains);

  const edges: Edge[] = [];
  // The root counts as visited from the start, so a cycle back to it terminates
  // rather than re-entering, and the selection never lists itself.
  const visited = new Set([request.rootModuleId]);
  let frontier = [request.rootModuleId];
  let hop = 0;
  let truncated = false;

  while (frontier.length > 0) {
    hop += 1;
    if (depth !== UNBOUNDED_CLOSURE_DEPTH && hop > depth) {
      // Something was still reachable when the bound stopped us. That is a
      // different answer from an exhausted graph and the console says so.
      truncated = true;
      break;
    }

    const next: string[] = [];
    for (const moduleId of frontier) {
      const manifest = request.manifests.get(moduleId);
      if (!manifest) continue;

      const optionalNames = optionalCapabilityNames(manifest);
      const bound = request.bindings?.get(moduleId);

      for (const target of planConsumerCleanup(moduleId, manifest, providerRows, providerStates)) {
        // A cycle walks back to the selection. Terminating the WALK there is not
        // enough: the edge is still real, and recording it would list the
        // selected module as one of its own dependencies. caddy requires
        // authentik and authentik requires caddy, so this is the ordinary case
        // on a real fleet rather than a pathological one.
        if (target.providerId === request.rootModuleId) continue;

        for (const capability of target.capabilityNames) {
          // A capability the consumer declared and never called into is not a
          // dependency. Following it would put a provider inside the closure on
          // the strength of a manifest line, which is a claim that the module is
          // standing on something it has never touched.
          if (bound && bound.get(capability) !== target.providerId) continue;

          edges.push({
            to: target.providerId,
            hop,
            capability,
            optional: optionalNames.has(capability),
          });
        }
        if (!visited.has(target.providerId)) {
          visited.add(target.providerId);
          next.push(target.providerId);
        }
      }
    }

    // The edges the manifests do not carry. Followed here, inside the same loop,
    // so a delegated provider gets its hop, its cycle check and its depth bound
    // from the one walk rather than from a second rule applied afterwards.
    //
    // Never optional: a packet has no alternative route to the internet, so a
    // delegation is the strongest kind of dependency there is.
    for (const moduleId of frontier) {
      for (const edge of delegationsOut.get(moduleId) ?? []) {
        if (edge.to === request.rootModuleId) continue;
        edges.push({ to: edge.to, hop, capability: edge.capability, optional: false });
        if (!visited.has(edge.to)) {
          visited.add(edge.to);
          next.push(edge.to);
        }
      }
    }

    frontier = next;
  }

  const nodes = collectNodes(edges);
  const reached = new Set([request.rootModuleId, ...nodes.map((node) => node.moduleId)]);

  return {
    nodes,
    chains: chains.filter((chain) => chain.moduleIds.some((id) => reached.has(id))),
    depth,
    truncated,
  };
}

/**
 * Fold the edge list into one node per module.
 *
 * A module is recorded at the SHORTEST hop that reached it, and is optional only
 * if no edge anywhere in the walk reached it by a required capability. Deciding
 * either from the first edge seen would make the answer depend on iteration
 * order.
 */
function collectNodes(edges: readonly Edge[]): ClosureNode[] {
  const byModule = new Map<string, { hop: number; via: Set<string>; anyRequired: boolean }>();

  for (const edge of edges) {
    const existing = byModule.get(edge.to);
    if (!existing) {
      byModule.set(edge.to, {
        hop: edge.hop,
        via: new Set([edge.capability]),
        anyRequired: !edge.optional,
      });
      continue;
    }
    existing.hop = Math.min(existing.hop, edge.hop);
    existing.via.add(edge.capability);
    existing.anyRequired = existing.anyRequired || !edge.optional;
  }

  return [...byModule.entries()]
    .map(([moduleId, v]) => ({
      moduleId,
      hop: v.hop,
      optional: !v.anyRequired,
      via: [...v.via].sort(),
    }))
    .sort((a, b) => a.hop - b.hop || a.moduleId.localeCompare(b.moduleId));
}