/**
 * The `Depends-on:` declaration parser (epic #321, slices #419/#420).
 *
 * A candidate issue can declare prerequisites it must not be dispatched
 * before: `Depends-on: #123` (a same-repo issue) or `Depends-on:
 * owner/repo#123` (an issue in a routed repository), repeatable one or more
 * per line. Admission reads every referenced issue's live tracker state and
 * holds the candidate while any prerequisite is open, so a worker is never
 * sent at work whose base is not yet merged.
 *
 * The parser is deliberately small and strict, the two halves of the contract:
 * the *marker* is matched case-insensitively (so `DEPENDS-ON`, `Depends-On`,
 * `depends-on` all declare), while the *references* are strict — a bare issue
 * number (`#123`) or a qualifying `owner/repo#123` with exactly two path
 * segments glued to the number. A marker line that carries no strict
 * reference — an empty `Depends-on:`, a bare non-numeric `Depends-on: #abc`,
 * or a slashed-but-unqualified form that is not `owner/repo#n` — is never a
 * usable prerequisite, so it is reported as `malformed` for the grooming flag
 * rather than guessed at, and the declaration it belongs to is ignored.
 *
 * The module also owns the dependency-graph cycle pass (#421): {@link
 * buildDependencyCycles} closes the graph over a pass's candidates and their
 * reachable `Depends-on:` targets, and names every cycle so admission can hold
 * the whole group rather than have an open first edge mask the cycle.
 */

import type { IssueState } from "./types.ts";

/** Canonical identity of one dependency-graph node: `owner/repo#n`. */
export interface DependencyNode {
  readonly repo: string;
  readonly issue: number;
}

/** Stable string key for {@link DependencyNode} — `owner/repo#n`. */
export function dependencyNodeKey(repo: string, issue: number): string {
  return `${repo}#${issue}`;
}

/** One issue's live facts, enough to follow a dependency edge from it. */
export interface DependencyRead {
  readonly state: IssueState;
  readonly body: string;
}

/**
 * Reads one issue's state + body in either the tracker repo or a routed repo,
 * or undefined when the repo is not a resolvable dependency target or the read
 * could not be completed. Both cases fail closed — no edge is added — rather
 * than ever synthesising a false cycle (#421).
 */
export type DependencyNodeReader = (
  repo: string,
  issue: number,
) => Promise<DependencyRead | undefined>;

/** Where a cross-repo `owner/repo#n` target resolves: the tracker repo, a
 *  routed repo, or nowhere (bounds traversal to the fleet's own repos). */
export type DependencyRepoResolver = (ownerRepo: string) => "tracker" | "routed" | undefined;

/** A detected dependency cycle, canonicalised so rotation or queue order cannot
 *  change its identity (and therefore cannot emit a new material event). */
export interface DependencyCycle {
  /** Member node keys (`owner/repo#n`), for membership checks. */
  readonly members: readonly string[];
  /** The cycle as an ordered path from the canonical start, closing on itself.
   *  The display is stable under rotation and queue order. */
  readonly path: readonly DependencyNode[];
  /** {@link path} rendered: same-repo nodes as `#n`, others as `owner/repo#n`. */
  readonly display: string;
  /** The tracker-repo issue this cycle is reported against: the lowest global
   *  tracker issue among the members. A cycle reachable only through routed
   *  nodes falls back to its lowest member issue. */
  readonly anchorIssue: number;
}

/** The output of one cycle pass over a set of candidates. */
export interface DependencyGraphResult {
  /** Node keys of every node on at least one detected cycle. */
  readonly cycleNodes: ReadonlySet<string>;
  /** The distinct cycles found, canonicalised and deduplicated. */
  readonly cycles: readonly DependencyCycle[];
}

export interface DependsOnDecl {
  /** Referenced same-repo prerequisite issue numbers, deduplicated,
   *  first-seen order. */
  readonly refs: readonly number[];
  /** Referenced cross-repo prerequisites (`owner/repo#n`), deduplicated,
   *  first-seen order. Admission resolves these against the fleet's routed
   *  repositories, never against the candidate's own repo (#420). */
  readonly crossRefs: readonly DependsOnCrossRef[];
  /** Marker-bearing lines that carried no strict reference (e.g.
   *  `Depends-on: #abc`). Bounded to what the body actually said, for the
   *  grooming flag's detail. */
  readonly malformed: readonly string[];
}

/**
 * A strict cross-repo reference. `repo` is the canonical `owner/repo` spelling
 * from the body, untouched, so admission can match it by identity against the
 * fleet's routed repositories rather than by guess.
 */
export interface DependsOnCrossRef {
  readonly repo: string;
  readonly issue: number;
}

/**
 * How a line is spelled: `depends-on`/`depends on`, optional whitespace, then
 * a `:` or `=` separator. The marker is matched case-insensitively; the value
 * (everything after the separator) is what the strict-reference rules apply
 * to. Anchored at the start of the (trimmed) line so a prose mention of
 * "Depends-on" mid-sentence is not a declaration.
 */
const MARKER = /^depends[-\s]?on\s*[:=]\s*(.*)$/i;

/** A strict same-repo reference is a bare `#` followed by digits — no repo
 *  qualifier, no words. The negative lookbehind means a `#<n>` glued to a
 *  word (e.g. `web#7` or `issue#5`) is not a bare reference: without the
 *  `owner/` segment it is neither a valid cross-repo ref nor a valid
 *  same-repo one, so it is flagged malformed rather than silently resolved in
 *  the candidate's own repo. */
const REF = /(?<![A-Za-z0-9._/-])#(\d+)/g;

/**
 * A strict cross-repo reference is `owner/repo#<n>` — exactly two path
 * segments (each a GitHub owner/repository charset run) glued to a bare issue
 * number, no whitespace. Scanned before {@link REF} and blanked out of the
 * value, so the trailing `#<n>` is never re-read as a *same-repo* reference:
 * the whole point of the qualified form is that it names a different
 * repository, and resolving it in the candidate's own repo is the #420 fake.
 */
const CROSS_REF = /([A-Za-z0-9][A-Za-z0-9._-]*)\/([A-Za-z0-9][A-Za-z0-9._-]*)#(\d+)/g;

export function parseDependsOn(body: string): DependsOnDecl {
  const refs: number[] = [];
  const seen = new Set<number>();
  const crossRefs: DependsOnCrossRef[] = [];
  const seenCross = new Set<string>();
  const malformed: string[] = [];
  for (const raw of body.split("\n")) {
    const line = raw.trim();
    if (line === "") continue;
    const match = MARKER.exec(line);
    if (match === null) continue;
    const value = match[1] ?? "";

    // Cross-repo references first, blanked out of the value so their `#<n>`
    // cannot also be collected as a same-repo reference below.
    let lineHadRef = false;
    const masked = value.replace(CROSS_REF, (whole, owner, name, number) => {
      const repo = `${owner}/${name}`;
      const n = Number(number);
      if (Number.isSafeInteger(n) && !seenCross.has(`${repo}#${n}`)) {
        seenCross.add(`${repo}#${n}`);
        crossRefs.push({ repo, issue: n });
      }
      lineHadRef = true;
      return " ".repeat(whole.length);
    });

    REF.lastIndex = 0;
    const found = [...masked.matchAll(REF)];
    for (const group of found) {
      const n = Number(group[1]!);
      if (Number.isSafeInteger(n) && !seen.has(n)) {
        seen.add(n);
        refs.push(n);
      }
      lineHadRef = true;
    }

    if (!lineHadRef) {
      // A marker line with no strict reference — same-repo or cross-repo — is
      // a malformed declaration: never crash, never silently claim — the
      // declaration is ignored and surfaced for grooming.
      malformed.push(line);
      continue;
    }
  }
  return { refs, crossRefs, malformed };
}

/**
 * Enumerate every dependency cycle reachable from an admission pass's
 * candidates. Built once per pass, before any per-candidate open-prerequisite
 * hold, so a candidate sitting on a cycle is held as `dependency-cycle` rather
 * than having its status masked by the first open edge (#421).
 *
 * The graph nodes are the candidates (bodies already parsed from `routed`,
 * never a network read) plus every issue they reach through `Depends-on:`
 * references — a bare `#n` resolves in the declaring node's own repo
 * (tracker or routed), a cross-repo `owner/repo#n` in the tracker or a
 * routed repo. Traversal is bounded in three ways:
 *   - references to a repo that is neither the tracker nor a routed repo are
 *     dropped before any read (they are the existing unroutable hold's job);
 *   - every node is expanded once, so each body/state read happens at most
 *     once per pass regardless of how many candidates reach it;
 *   - a closed node is terminal: it never propagates a cycle, because a
 *     dependency that is already done cannot hold anyone open.
 * A node whose state or body cannot be read fails closed — it adds no edge and
 * is never mistaken for a cycle; the per-candidate path then holds its
 * originator on the existing dependency-unreadable route.
 *
 * Cycle membership is the graph's strongly connected components (Tarjan): a
 * node sits on some directed cycle exactly when its component has more than
 * one node or a self-edge, so overlapping cycles cannot hide a member behind
 * an already-explored subtree. Each cyclic component is one cycle identity,
 * with a deterministic simple path for status/digest.
 */
export async function buildDependencyCycles(
  candidates: ReadonlyArray<{ repo: string; issue: number; body: string }>,
  trackerRepo: string,
  resolveRepo: DependencyRepoResolver,
  read: DependencyNodeReader,
): Promise<DependencyGraphResult> {
  const candidateBody = new Map<string, string>();
  for (const c of candidates) {
    candidateBody.set(dependencyNodeKey(c.repo, c.issue), c.body);
  }

  // Materialise the reachable graph once: node key -> outgoing targets. A key
  // present in `adj` is expanded — a candidate carries its body, a
  // non-candidate is read at most once, and an unreadable or closed node is
  // terminal (present, with no edges), so it is never read or re-expanded.
  const adj = new Map<string, DependencyNode[]>();
  const nodeOf = new Map<string, DependencyNode>();

  const expand = async (node: DependencyNode): Promise<void> => {
    const key = dependencyNodeKey(node.repo, node.issue);
    if (adj.has(key)) return;
    let body = candidateBody.get(key);
    if (body === undefined) {
      // Non-candidate node: read it fresh (once), fail closed on any doubt.
      const r = await read(node.repo, node.issue);
      if (r === undefined || r.state === "closed") {
        // Unreadable never synthesises a cycle; a closed dependency is terminal.
        adj.set(key, []);
        nodeOf.set(key, { repo: node.repo, issue: node.issue });
        return;
      }
      body = r.body;
    }

    const decl = parseDependsOn(body);
    const targets: DependencyNode[] = [];
    // A bare `#n` resolves in the declaring node's OWN repo: a body read from
    // `acme/web#7` declares `acme/web#n`, never the tracker repo's #n.
    for (const ref of decl.refs) {
      targets.push({ repo: node.repo, issue: ref });
    }
    for (const cref of decl.crossRefs) {
      const where = resolveRepo(cref.repo);
      if (where === "tracker") targets.push({ repo: trackerRepo, issue: cref.issue });
      else if (where === "routed") targets.push({ repo: cref.repo, issue: cref.issue });
      // unresolved repos are dropped before any read: bounds traversal to the
      // fleet's own tracker/routed repos (#421).
    }
    adj.set(key, targets);
    nodeOf.set(key, { repo: node.repo, issue: node.issue });
    for (const t of targets) {
      await expand(t);
    }
  };

  for (const c of candidates) {
    await expand({ repo: c.repo, issue: c.issue });
  }

  // Tarjan's strongly connected components over the materialised graph. Every
  // node on some directed cycle is in a cyclic component, so membership is
  // complete where a single DFS path would miss a member behind an
  // already-explored subtree (1 -> {2,3}, 3 -> 2, 2 -> 1: 3 is on the cycle
  // 1 -> 3 -> 2 -> 1 even though the direct 1 <-> 2 pair is found first).
  let nextIndex = 0;
  const index = new Map<string, number>();
  const low = new Map<string, number>();
  const onStack = new Set<string>();
  const stack: string[] = [];
  const components: string[][] = [];

  const strongConnect = (key: string): void => {
    index.set(key, nextIndex);
    low.set(key, nextIndex);
    nextIndex += 1;
    stack.push(key);
    onStack.add(key);
    for (const t of adj.get(key) ?? []) {
      const targetKey = dependencyNodeKey(t.repo, t.issue);
      if (!index.has(targetKey)) {
        strongConnect(targetKey);
        low.set(key, Math.min(low.get(key)!, low.get(targetKey)!));
      } else if (onStack.has(targetKey)) {
        low.set(key, Math.min(low.get(key)!, index.get(targetKey)!));
      }
    }
    if (low.get(key) === index.get(key)) {
      const component: string[] = [];
      let w: string;
      do {
        w = stack.pop()!;
        onStack.delete(w);
        component.push(w);
      } while (w !== key);
      components.push(component);
    }
  };
  for (const key of adj.keys()) {
    if (!index.has(key)) strongConnect(key);
  }

  /** A deterministic simple directed cycle inside one cyclic component: DFS
   *  from the smallest member with children in key order; the first back edge
   *  closes a path. A true cyclic component always yields one — every member
   *  reaches every other, so the search cannot finish without crossing an
   *  ancestor. */
  const findCyclePath = (
    start: DependencyNode,
    inComponent: ReadonlySet<string>,
  ): readonly DependencyNode[] | undefined => {
    const path: DependencyNode[] = [start];
    const position = new Map<string, number>([
      [dependencyNodeKey(start.repo, start.issue), 0],
    ]);
    const descend = (cur: DependencyNode): readonly DependencyNode[] | undefined => {
      const children = (adj.get(dependencyNodeKey(cur.repo, cur.issue)) ?? [])
        .filter((t) => inComponent.has(dependencyNodeKey(t.repo, t.issue)))
        .sort((a, b) => {
          const ka = dependencyNodeKey(a.repo, a.issue);
          const kb = dependencyNodeKey(b.repo, b.issue);
          return ka < kb ? -1 : ka > kb ? 1 : 0;
        });
      for (const child of children) {
        const childKey = dependencyNodeKey(child.repo, child.issue);
        const at = position.get(childKey);
        if (at !== undefined) {
          // Back edge: the path from the ancestor to here, closed on `child`.
          return [...path.slice(at), child];
        }
        position.set(childKey, path.length);
        path.push(child);
        const found = descend(child);
        if (found !== undefined) return found;
        path.pop();
        position.delete(childKey);
      }
      return undefined;
    };
    return descend(start);
  };

  const cycles: DependencyCycle[] = [];
  for (const component of components) {
    const members = [...component].sort();
    const hasSelfEdge = members.some((k) =>
      (adj.get(k) ?? []).some((t) => dependencyNodeKey(t.repo, t.issue) === k),
    );
    if (members.length === 1 && !hasSelfEdge) continue; // terminal or acyclic
    // Canonical start: the smallest member by owner/repo#n spelling, so
    // rotation and queue order never produce a different identity.
    const path = findCyclePath(nodeOf.get(members[0]!)!, new Set(component));
    if (path === undefined) continue; // unreachable for a cyclic component; never fabricate
    const display = path
      .map((n) => (n.repo === trackerRepo ? `#${n.issue}` : `${n.repo}#${n.issue}`))
      .join(" -> ");
    const trackerMembers = members
      .map((k) => k.split("#") as [string, string])
      .filter(([repo]) => repo === trackerRepo)
      .map(([, issue]) => Number(issue));
    const anchorIssue =
      trackerMembers.length > 0
        ? Math.min(...trackerMembers)
        : Math.min(...members.map((k) => Number(k.split("#")[1])));

    cycles.push({ members, path, display, anchorIssue });
  }

  const cycleNodes = new Set<string>();
  for (const cyc of cycles) for (const m of cyc.members) cycleNodes.add(m);
  return { cycleNodes, cycles };
}