/**
 * Unit tests for `finalize` (RFC #909 Ring 2 SHARED #915).
 *
 * Covers: acyclic chain · single-SCC cycle · multi-SCC · wildcard
 * expansion · re-export flattening · dynamic import passthrough/linking ·
 * side-effect imports · bounded fixpoint cap · module-scope binding
 * materialization · unresolved target · external target · provider
 * `mergeBindings` precedence.
 */

import { describe, it, expect } from 'vitest';
import {
  finalize,
  type FinalizeFile,
  type FinalizeHooks,
  type ParsedImport,
  type BindingRef,
  type SymbolDefinition,
  type ScopeId,
} from 'gitnexus-shared';

// ─── Test helpers ───────────────────────────────────────────────────────────

const def = (
  nodeId: string,
  type: SymbolDefinition['type'] = 'Class',
  qualifiedName?: string,
): SymbolDefinition => ({
  nodeId,
  filePath: 'x',
  type,
  ...(qualifiedName !== undefined ? { qualifiedName } : {}),
});

const file = (
  filePath: string,
  localDefs: SymbolDefinition[] = [],
  parsedImports: ParsedImport[] = [],
): FinalizeFile => ({
  filePath,
  moduleScope: `scope:${filePath}#1:0-9999:0:Module`,
  localDefs: localDefs.map((d) => ({ ...d, filePath })),
  parsedImports,
});

/** Simple hook set: `resolveImportTarget` does a direct path lookup; wildcard
 *  expansion returns the concrete names from the target's own local defs;
 *  `mergeBindings` appends (no precedence logic). */
const defaultHooks = (files: readonly FinalizeFile[]): FinalizeHooks => ({
  resolveImportTarget(targetRaw) {
    if (targetRaw === null || targetRaw.length === 0) return null;
    return files.some((f) => f.filePath === targetRaw) ? targetRaw : null;
  },
  expandsWildcardTo(targetModuleScope) {
    const target = files.find((f) => f.moduleScope === targetModuleScope);
    if (target === undefined) return [];
    return target.localDefs.map((d) => deriveSimple(d)).filter((n): n is string => n !== null);
  },
  mergeBindings(existing, incoming) {
    return [...existing, ...incoming];
  },
});

function deriveSimple(d: SymbolDefinition): string | null {
  const q = d.qualifiedName;
  if (q === undefined || q.length === 0) return null;
  const dot = q.lastIndexOf('.');
  return dot === -1 ? q : q.slice(dot + 1);
}

const named = (localName: string, importedName: string, targetRaw: string): ParsedImport => ({
  kind: 'named',
  localName,
  importedName,
  targetRaw,
});

const aliased = (
  localName: string,
  importedName: string,
  alias: string,
  targetRaw: string,
): ParsedImport => ({ kind: 'alias', localName, importedName, alias, targetRaw });

const namespace = (localName: string, importedName: string, targetRaw: string): ParsedImport => ({
  kind: 'namespace',
  localName,
  importedName,
  targetRaw,
});

const reexport = (localName: string, importedName: string, targetRaw: string): ParsedImport => ({
  kind: 'reexport',
  localName,
  importedName,
  targetRaw,
});

const wildcard = (targetRaw: string): ParsedImport => ({ kind: 'wildcard', targetRaw });

/** A named import that also republishes the name — see `reexportsName` on `ParsedImport`. */
const namedReexporting = (
  localName: string,
  importedName: string,
  targetRaw: string,
): ParsedImport => ({
  kind: 'named',
  localName,
  importedName,
  targetRaw,
  reexportsName: true,
});

/** The `from m import X as Y` form of {@link namedReexporting}. */
const aliasReexporting = (
  localName: string,
  importedName: string,
  targetRaw: string,
): ParsedImport => ({
  kind: 'alias',
  localName,
  importedName,
  alias: localName,
  targetRaw,
  reexportsName: true,
});

const dynamic = (localName: string, targetRaw: string | null): ParsedImport => ({
  kind: 'dynamic-unresolved',
  localName,
  targetRaw,
});

const dynamicResolved = (targetRaw: string): ParsedImport => ({
  kind: 'dynamic-resolved',
  targetRaw,
});

const sideEffect = (targetRaw: string): ParsedImport => ({ kind: 'side-effect', targetRaw });

const firstImport = (out: ReturnType<typeof finalize>, scope: ScopeId) => {
  const imports = out.imports.get(scope);
  return imports?.[0];
};

const bindingsFor = (
  out: ReturnType<typeof finalize>,
  scope: ScopeId,
  name: string,
): readonly BindingRef[] => {
  const scopeBindings = out.bindings.get(scope);
  return scopeBindings?.get(name) ?? [];
};

// ─── Tests ──────────────────────────────────────────────────────────────────

describe('finalize', () => {
  describe('trivial / acyclic', () => {
    it('handles an empty workspace', () => {
      const out = finalize({ files: [], workspaceIndex: undefined }, defaultHooks([]));
      expect(out.stats.totalFiles).toBe(0);
      expect(out.stats.totalEdges).toBe(0);
      expect(out.sccs).toEqual([]);
    });

    it('resolves a single named import across two files', () => {
      const b = file('b', [def('def:b.User', 'Class', 'b.User')]);
      const a = file('a', [], [named('User', 'User', 'b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));

      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.kind).toBe('named');
      expect(edge.targetFile).toBe('b');
      expect(edge.targetModuleScope).toBe(b.moduleScope);
      expect(edge.targetDefId).toBe('def:b.User');
      expect(edge.linkStatus).toBeUndefined();
      expect(out.stats.linkedEdges).toBe(1);
      expect(out.stats.unresolvedEdges).toBe(0);
    });

    it('marks an edge unresolved when target file cannot be resolved', () => {
      const a = file('a', [], [named('User', 'User', 'external-pkg')]);
      const out = finalize({ files: [a], workspaceIndex: undefined }, defaultHooks([a]));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.linkStatus).toBe('unresolved');
      expect(edge.targetFile).toBeNull();
    });

    it('marks an edge unresolved when target file exists but name is not exported', () => {
      const b = file('b', [def('def:b.Other', 'Class', 'b.Other')]);
      const a = file('a', [], [named('User', 'User', 'b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.linkStatus).toBe('unresolved');
      // targetFile still known — unresolvability is at the name level.
      expect(edge.targetFile).toBe('b');
    });

    it('passes dynamic-unresolved edges through without linking', () => {
      const a = file('a', [], [dynamic('', 'runtime.computed')]);
      const out = finalize({ files: [a], workspaceIndex: undefined }, defaultHooks([a]));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.kind).toBe('dynamic-unresolved');
      expect(edge.targetFile).toBeNull();
      expect(edge.linkStatus).toBeUndefined();
    });

    it('links dynamic-resolved imports as file-level edges without bindings', () => {
      const feature = file('feature', [def('def:feature.Feature', 'Class', 'feature.Feature')]);
      const app = file('app', [], [dynamicResolved('feature')]);
      const files = [app, feature];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));

      const edge = firstImport(out, app.moduleScope)!;
      expect(edge.kind).toBe('dynamic-resolved');
      expect(edge.targetFile).toBe('feature');
      expect(edge.linkStatus).toBeUndefined();
      expect(edge.targetDefId).toBeUndefined();
      expect(bindingsFor(out, app.moduleScope, 'Feature')).toEqual([]);
      expect(out.stats.linkedEdges).toBe(1);
    });

    it('links side-effect imports as file-level edges without bindings', () => {
      const polyfill = file('polyfill', [
        def('def:polyfill.install', 'Function', 'polyfill.install'),
      ]);
      const app = file('app', [], [sideEffect('polyfill')]);
      const files = [app, polyfill];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));

      const edge = firstImport(out, app.moduleScope)!;
      expect(edge.kind).toBe('side-effect');
      expect(edge.localName).toBe('');
      expect(edge.targetFile).toBe('polyfill');
      expect(edge.linkStatus).toBeUndefined();
      expect(edge.targetDefId).toBeUndefined();
      expect(bindingsFor(out, app.moduleScope, 'install')).toEqual([]);
      expect(out.stats.linkedEdges).toBe(1);
    });
  });

  describe('cycles + bounded fixpoint', () => {
    it('finalizes a two-file cycle (A → B → A) without hanging', () => {
      const a = file('a', [def('def:a.X', 'Class', 'a.X')], [named('Y', 'Y', 'b')]);
      const b = file('b', [def('def:b.Y', 'Class', 'b.Y')], [named('X', 'X', 'a')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));

      const aEdge = firstImport(out, a.moduleScope)!;
      const bEdge = firstImport(out, b.moduleScope)!;
      expect(aEdge.targetDefId).toBe('def:b.Y');
      expect(bEdge.targetDefId).toBe('def:a.X');
      expect(out.stats.sccCount).toBeGreaterThanOrEqual(1);
    });

    it('packs cyclic files into a single SCC with isCycle=true', () => {
      const a = file('a', [def('def:a.X', 'Class', 'a.X')], [named('Y', 'Y', 'b')]);
      const b = file('b', [def('def:b.Y', 'Class', 'b.Y')], [named('X', 'X', 'a')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const cycles = out.sccs.filter((scc) => scc.isCycle);
      expect(cycles.length).toBe(1);
      expect(cycles[0]!.files.length).toBe(2);
      expect(new Set(cycles[0]!.files)).toEqual(new Set(['a', 'b']));
    });

    it('separates disjoint SCCs', () => {
      // a↔b cycle, c↔d cycle — disjoint.
      const a = file('a', [def('def:a.X', 'Class', 'a.X')], [named('Y', 'Y', 'b')]);
      const b = file('b', [def('def:b.Y', 'Class', 'b.Y')], [named('X', 'X', 'a')]);
      const c = file('c', [def('def:c.P', 'Class', 'c.P')], [named('Q', 'Q', 'd')]);
      const d = file('d', [def('def:d.Q', 'Class', 'd.Q')], [named('P', 'P', 'c')]);
      const files = [a, b, c, d];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const cycleSCCs = out.sccs.filter((scc) => scc.isCycle);
      expect(cycleSCCs.length).toBe(2);
    });

    it('reports stats distinguishing linked from unresolved edges in a cycle', () => {
      const a = file(
        'a',
        [def('def:a.X', 'Class', 'a.X')],
        [named('Y', 'Y', 'b'), named('Ghost', 'Ghost', 'b')],
      );
      const b = file('b', [def('def:b.Y', 'Class', 'b.Y')], [named('X', 'X', 'a')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      expect(out.stats.linkedEdges).toBe(2); // a→b.Y and b→a.X resolve
      expect(out.stats.unresolvedEdges).toBe(1); // a→b.Ghost doesn't
    });

    it('transitions an intra-SCC edge to linkStatus=unresolved when the cap is reached', () => {
      // A↔B cycle; A imports a name that B never exports. The file-level
      // target resolves (b exists), but the name-level lookup never
      // succeeds, so the fixpoint exhausts its cap and we fall through to
      // `linkStatus: 'unresolved'` (distinct from `targetFile: null`).
      const a = file(
        'a',
        [def('def:a.X', 'Class', 'a.X')],
        [named('Ghost', 'Ghost', 'b'), named('Y', 'Y', 'b')],
      );
      const b = file('b', [def('def:b.Y', 'Class', 'b.Y')], [named('X', 'X', 'a')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));

      const aEdges = out.imports.get(a.moduleScope) ?? [];
      const ghost = aEdges.find((e) => e.localName === 'Ghost');
      expect(ghost).toBeDefined();
      // Cap-hit distinction: file target is known, but name never resolved.
      expect(ghost!.targetFile).toBe('b');
      expect(ghost!.linkStatus).toBe('unresolved');
      expect(ghost!.targetDefId).toBeUndefined();
    });
  });

  describe('wildcard expansion', () => {
    it('expands `wildcard` into one ImportEdge per exported name', () => {
      const b = file('b', [
        def('def:b.X', 'Class', 'b.X'),
        def('def:b.Y', 'Class', 'b.Y'),
        def('def:b.Z', 'Class', 'b.Z'),
      ]);
      const a = file('a', [], [wildcard('b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edges = out.imports.get(a.moduleScope) ?? [];
      expect(edges.length).toBe(3);
      expect(edges.every((e) => e.kind === 'wildcard-expanded')).toBe(true);
      expect(new Set(edges.map((e) => e.localName))).toEqual(new Set(['X', 'Y', 'Z']));
      expect(new Set(edges.map((e) => e.targetDefId))).toEqual(
        new Set(['def:b.X', 'def:b.Y', 'def:b.Z']),
      );
    });

    it('leaves a wildcard unresolved when the target file cannot be resolved', () => {
      const a = file('a', [], [wildcard('external-pkg')]);
      const out = finalize({ files: [a], workspaceIndex: undefined }, defaultHooks([a]));
      const edges = out.imports.get(a.moduleScope) ?? [];
      expect(edges.length).toBe(1);
      expect(edges[0]!.linkStatus).toBe('unresolved');
    });

    it('expanded bindings land at `origin: wildcard`', () => {
      const b = file('b', [def('def:b.X', 'Class', 'b.X')]);
      const a = file('a', [], [wildcard('b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const bindings = bindingsFor(out, a.moduleScope, 'X');
      expect(bindings.length).toBeGreaterThanOrEqual(1);
      const imported = bindings.find((br) => br.origin === 'wildcard');
      expect(imported).toBeDefined();
      expect(imported!.def.nodeId).toBe('def:b.X');
    });
  });

  describe('re-export flattening', () => {
    it('sets transitiveVia on reexport edges', () => {
      const c = file('c', [def('def:c.X', 'Class', 'c.X')]);
      const b = file('b', [], [reexport('X', 'X', 'c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const reexportEdge = firstImport(out, b.moduleScope)!;
      expect(reexportEdge.kind).toBe('reexport');
      expect(reexportEdge.transitiveVia).toEqual(['c']);
    });

    it('multi-hop re-export chains resolve via the precomputed closure even when intermediate files do not surface the name', () => {
      // Contract (see FinalizeFile.localDefs doc): `finalize` first looks
      // up `importedName` in `B.localDefs`. If B only has
      //   export { X } from './C'
      // and does NOT surface X in its own localDefs, finalize falls back
      // to the precomputed re-export closure (`buildReexportClosures`),
      // which encodes every name reachable through B's reexport/wildcard
      // chain. The lookup is O(1) and inherits the leaf `targetDefId`.
      // SCC-condensed iteration handles cyclic chains structurally.
      //
      // The "thin" variant (B does not surface X) resolves to C's def
      // via the re-export chain. The "thick" variant (B has its own X
      // local def) short-circuits to B's local def — surfacing the name
      // is a valid optimization that bypasses the recursive crawl, but
      // it can also intentionally shadow the re-export.
      const c = file('c', [def('def:c.X', 'Class', 'c.X')]);

      // Variant 1: B does NOT include X in its own localDefs.
      const bThin = file('b', [], [reexport('X', 'X', 'c')]);
      const aThin = file('a', [], [named('X', 'X', 'b')]);
      const thinFiles = [aThin, bThin, c];
      const thinOut = finalize(
        { files: thinFiles, workspaceIndex: undefined },
        defaultHooks(thinFiles),
      );
      const thinEdge = firstImport(thinOut, aThin.moduleScope)!;
      expect(thinEdge.linkStatus).toBeUndefined();
      expect(thinEdge.targetDefId).toBe('def:c.X');
      // `transitiveVia` records the chain: through B (target) into C (leaf).
      expect(thinEdge.transitiveVia).toEqual(['b', 'c']);

      // Variant 2: B surfaces X via its OWN localDefs (distinct nodeId
      // from C's X) → direct B.localDefs lookup short-circuits the
      // closure consult. This is the "shadowing" optimization: when B
      // explicitly surfaces a name, importers see B's def, not the
      // upstream one. `transitiveVia` is undefined since no chain walk
      // happened.
      const bThick = file('b', [def('def:b.X', 'Class', 'b.X')], [reexport('X', 'X', 'c')]);
      const aThick = file('a', [], [named('X', 'X', 'b')]);
      const thickFiles = [aThick, bThick, c];
      const thickOut = finalize(
        { files: thickFiles, workspaceIndex: undefined },
        defaultHooks(thickFiles),
      );
      const thickEdge = firstImport(thickOut, aThick.moduleScope)!;
      expect(thickEdge.linkStatus).toBeUndefined();
      expect(thickEdge.targetDefId).toBe('def:b.X');
      expect(thickEdge.transitiveVia).toBeUndefined();
    });

    it('resolves a 3-hop re-export chain (a → b → c → d) where intermediates do not surface the name', () => {
      const d = file('d', [def('def:d.X', 'Class', 'd.X')]);
      const c = file('c', [], [reexport('X', 'X', 'd')]);
      const b = file('b', [], [reexport('X', 'X', 'c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c, d];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.linkStatus).toBeUndefined();
      expect(edge.targetDefId).toBe('def:d.X');
      expect(edge.transitiveVia).toEqual(['b', 'c', 'd']);
    });

    // ── Languages with no dedicated re-export form (Python) ──────────────
    // Contract and rationale live on `reexportsName` in `ParsedImport`.
    it('resolves through a named import flagged reexportsName (Python __init__.py surface)', () => {
      const c = file('c', [def('def:c.X', 'Function', 'c.X')]);
      // `pkg/__init__.py`: re-publishes X without surfacing it in localDefs.
      const b = file('b', [], [namedReexporting('X', 'X', 'c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.linkStatus).toBeUndefined();
      expect(edge.targetDefId).toBe('def:c.X');
      expect(edge.transitiveVia).toEqual(['b', 'c']);
    });

    it('leaves a plain named import out of the closure (no reexportsName → unchanged behavior)', () => {
      // Negative control: this is the pre-existing behavior every language
      // without the flag still gets. Only the flag opts a named import in, so
      // adding it cannot silently widen resolution for TS/Java/Go/etc.
      const c = file('c', [def('def:c.X', 'Function', 'c.X')]);
      const b = file('b', [], [named('X', 'X', 'c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.targetDefId).toBeUndefined();
    });

    it('resolves a 3-hop chain of reexportsName named imports', () => {
      // `pkg/__init__.py` → `pkg/sub/__init__.py` → defining module: the shape
      // a nested Python package produces.
      const d = file('d', [def('def:d.X', 'Function', 'd.X')]);
      const c = file('c', [], [namedReexporting('X', 'X', 'd')]);
      const b = file('b', [], [namedReexporting('X', 'X', 'c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c, d];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.targetDefId).toBe('def:d.X');
      expect(edge.transitiveVia).toEqual(['b', 'c', 'd']);
    });

    it('keys the closure by the published alias for `from m import X as Y`', () => {
      // `from c import X as Y` publishes `Y`, so an importer asking for Y must
      // reach X's definition, and one asking for X must not.
      const c = file('c', [def('def:c.X', 'Function', 'c.X')]);
      const b = file('b', [], [aliasReexporting('Y', 'X', 'c')]);
      const aY = file('a', [], [named('Y', 'Y', 'b')]);
      const filesY = [aY, b, c];
      const outY = finalize({ files: filesY, workspaceIndex: undefined }, defaultHooks(filesY));
      const edgeY = firstImport(outY, aY.moduleScope)!;
      expect(edgeY.targetDefId).toBe('def:c.X');
      // Path as well as destination: reaching `def:c.X` by any other route
      // would mean the closure was keyed by `importedName`, the exact bug
      // this test exists to catch.
      expect(edgeY.transitiveVia).toEqual(['b', 'c']);

      const aX = file('a', [], [named('X', 'X', 'b')]);
      const filesX = [aX, b, c];
      const outX = finalize({ files: filesX, workspaceIndex: undefined }, defaultHooks(filesX));
      expect(firstImport(outX, aX.moduleScope)!.targetDefId).toBeUndefined();
    });

    it('threads a definition out of a reexportsName cycle (package __init__ cycle)', () => {
      // b and c re-export from each other (`Y`), the shape two package
      // `__init__.py` files that import from each other produce. `X` enters
      // the cycle at c and must reach d's real def through it.
      //
      // The cycle needs a terminal def to be worth asserting on: with no
      // `SymbolDefinition` anywhere in the fixture, `toBeUndefined()` holds
      // for a correct implementation, a reverted one, and a broken one alike.
      const d = file('d', [def('def:d.X', 'Function', 'd.X')]);
      const c = file('c', [], [namedReexporting('X', 'X', 'd'), namedReexporting('Y', 'Y', 'b')]);
      const b = file('b', [], [namedReexporting('X', 'X', 'c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c, d];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.targetDefId).toBe('def:d.X');
      expect(edge.transitiveVia).toEqual(['b', 'c', 'd']);
    });

    it('drops a name two reexportsName imports publish from different files', () => {
      // CPython rebinds, so `from .v2 import Client` is the live `Client` and
      // declaration-order first-wins would attribute every importer to the
      // dead v1. Last-wins is no better — a `try:`/`except ImportError:` or
      // `if sys.version_info` pair runs exactly one branch and which is not
      // decidable here — so the ambiguous name is dropped and the importer
      // stays unresolved, the pre-#2864 answer.
      const v1 = file('v1', [def('def:v1.Client', 'Class', 'v1.Client')]);
      const v2 = file('v2', [def('def:v2.Client', 'Class', 'v2.Client')]);
      const pkg = file(
        'pkg',
        [],
        [namedReexporting('Client', 'Client', 'v1'), namedReexporting('Client', 'Client', 'v2')],
      );
      const a = file('a', [], [named('Client', 'Client', 'pkg')]);
      const files = [a, pkg, v1, v2];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.targetDefId).toBeUndefined();
      expect(edge.linkStatus).toBe('unresolved');
      // The file-level dependency is unaffected — only the symbol-level
      // attribution is withheld.
      expect(edge.targetFile).toBe('pkg');
    });

    it('keeps a name two reexportsName imports publish from the SAME file', () => {
      // Duplicate imports of one target are not ambiguous, so the
      // drop-on-collision rule must not fire on them.
      const impl = file('impl', [def('def:impl.X', 'Function', 'impl.X')]);
      const pkg = file(
        'pkg',
        [],
        [namedReexporting('X', 'X', 'impl'), namedReexporting('X', 'X', 'impl')],
      );
      const a = file('a', [], [named('X', 'X', 'pkg')]);
      const files = [a, pkg, impl];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      expect(firstImport(out, a.moduleScope)!.targetDefId).toBe('def:impl.X');
    });

    it('does not let a wildcard refill an ambiguous name', () => {
      // Named re-exports take precedence over wildcards, so suppressing only
      // the named loop would hand the name to `from .other import *` and
      // reinstate an arbitrary winner through the back door.
      const v1 = file('v1', [def('def:v1.Client', 'Class', 'v1.Client')]);
      const v2 = file('v2', [def('def:v2.Client', 'Class', 'v2.Client')]);
      const other = file('other', [def('def:other.Client', 'Class', 'other.Client')]);
      const pkg = file(
        'pkg',
        [],
        [
          namedReexporting('Client', 'Client', 'v1'),
          namedReexporting('Client', 'Client', 'v2'),
          wildcard('other'),
        ],
      );
      const a = file('a', [], [named('Client', 'Client', 'pkg')]);
      const files = [a, pkg, v1, v2, other];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      expect(firstImport(out, a.moduleScope)!.targetDefId).toBeUndefined();
    });

    it('caps transitiveVia at 32 on a deep chain and marks it truncated', () => {
      // Each hop copies the inherited path, so an uncapped chain is O(depth^2)
      // in time and retained memory. At depth 400 the cap is worth 67 -> 25 ms
      // and 145 -> 40 MB; the def it resolves to must not change.
      //
      // The truncated shape is fully determined: `extendVia` keeps the head,
      // 30 inherited entries, and the marker — so it is 32 entries naming the
      // nearest 31 hops, for any depth past the cap.
      const depth = 60;
      const files = [file('leaf', [def('def:leaf.X', 'Function', 'leaf.X')])];
      let prev = 'leaf';
      for (let d = 0; d < depth; d++) {
        files.push(file(`hop${d}`, [], [namedReexporting('X', 'X', prev)]));
        prev = `hop${d}`;
      }
      files.push(file('app', [], [named('X', 'X', prev)]));
      const app = files[files.length - 1]!;
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, app.moduleScope)!;
      expect(edge.targetDefId).toBe('def:leaf.X');
      const expected = [...Array.from({ length: 31 }, (_, i) => `hop${depth - 1 - i}`), '…'];
      expect(edge.transitiveVia).toEqual(expected);
      expect(edge.transitiveVia).toHaveLength(32);
    });

    it('leaves transitiveVia intact for chains under the cap', () => {
      const d = file('d', [def('def:d.X', 'Function', 'd.X')]);
      const c = file('c', [], [namedReexporting('X', 'X', 'd')]);
      const b = file('b', [], [namedReexporting('X', 'X', 'c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c, d];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      expect(firstImport(out, a.moduleScope)!.transitiveVia).toEqual(['b', 'c', 'd']);
    });

    it('leaves a reexportsName import reclassified to namespace out of the closure', () => {
      // Python's `from . import logger`: the provider's `isNamespaceImport`
      // hook reclassifies the draft to `namespace`, which aliases the target
      // MODULE and publishes no name. Admitting it republished whatever def
      // shared the module's simple name — for `logger.py` holding a
      // module-level `logger = logging.getLogger(...)`, importers of
      // `from pkg import logger` bound to that Variable instead of the module.
      const logger = file('logger', [def('def:logger.logger', 'Variable', 'logger.logger')]);
      const pkg = file('pkg', [], [namedReexporting('logger', 'logger', 'logger')]);
      const a = file('a', [], [named('logger', 'logger', 'pkg')]);
      const files = [a, pkg, logger];
      const hooks = {
        ...defaultHooks(files),
        isNamespaceImport: (imp: ParsedImport, targetFile: string | null) =>
          targetFile === 'logger' && imp.kind === 'named' && imp.localName === 'logger',
      };
      const out = finalize({ files, workspaceIndex: undefined }, hooks);
      expect(firstImport(out, a.moduleScope)!.targetDefId).toBeUndefined();
    });

    it('terminates without infinite recursion when re-exports cycle back through the chain', () => {
      // Cycle: b re-exports from c, c re-exports from b. Neither surfaces
      // X. The SCC-condensed closure builder lumps b+c into one cyclic
      // SCC and runs a bounded fixpoint inside it; with no terminal def
      // anywhere in the cycle, the closure entry for X never appears
      // and the consuming edge is correctly marked unresolved. No call
      // stack involvement at any point.
      const c = file('c', [], [reexport('X', 'X', 'b')]);
      const b = file('b', [], [reexport('X', 'X', 'c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.targetFile).toBe('b');
      expect(edge.linkStatus).toBe('unresolved');
      expect(edge.targetDefId).toBeUndefined();
    });

    it('falls through wildcard re-exports via the precomputed closure', () => {
      // B has `export * from './c'` (wildcard re-export). A imports `X`
      // from B. The closure builder fans out the wildcard at B by
      // copying every name from C's localDefs (and C's own closure)
      // into B's closure, so the lookup at finalize time is O(1).
      const c = file('c', [def('def:c.X', 'Class', 'c.X')]);
      const b = file('b', [], [wildcard('c')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.linkStatus).toBeUndefined();
      expect(edge.targetDefId).toBe('def:c.X');
    });

    it('resolves arbitrarily deep re-export chains without stack overflow (1000 hops, fully linked)', () => {
      // Build a 1000-link chain a₀ → a₁ → … → a₁₀₀₀, where each
      // intermediate is `export { X } from './aₙ₊₁'`. Only the last
      // file holds the actual `def:X`. The legacy recursive
      // implementation needed `MAX_REEXPORT_DEPTH=100` purely as a
      // call-stack ceiling (anything deeper would crash); the new
      // SCC-condensed iterative closure resolves the entire chain
      // structurally with zero stack involvement. Asserting full
      // resolution + accurate `transitiveVia` proves both that the
      // recursion is gone AND that the closure correctly inherits
      // the leaf def across all hops.
      const CHAIN_LEN = 1000;
      const chain: FinalizeFile[] = [];
      for (let i = 0; i <= CHAIN_LEN; i++) {
        const fp = `chain${i}`;
        if (i === CHAIN_LEN) {
          chain.push(file(fp, [def(`def:chain${i}.X`, 'Class', `chain${i}.X`)]));
        } else {
          chain.push(file(fp, [], [reexport('X', 'X', `chain${i + 1}`)]));
        }
      }
      const consumer = file('consumer', [], [named('X', 'X', 'chain1')]);
      const files = [consumer, ...chain];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, consumer.moduleScope)!;
      expect(edge.targetFile).toBe('chain1');
      expect(edge.linkStatus).toBeUndefined();
      expect(edge.targetDefId).toBe(`def:chain${CHAIN_LEN}.X`);
      // `transitiveVia` records the path the closure walked, now bounded by
      // `MAX_VIA_LENGTH` — copying the inherited array at every hop is
      // O(depth^2) in time and retained memory, and at this depth that is the
      // dominant cost of the pass. Full resolution above is the load-bearing
      // assertion and is unchanged: the chain is still walked end to end, only
      // the provenance array is summarized. `transitiveVia` has no production
      // reader; it is diagnostic.
      expect(edge.transitiveVia).toEqual([
        ...Array.from({ length: 31 }, (_, i) => `chain${i + 1}`),
        '…',
      ]);
      expect(edge.transitiveVia).toHaveLength(32);
    });

    it('first-match-wins when the closure encounters multiple sources for the same name', () => {
      // B re-exports X from BOTH c and d. The closure builder walks
      // re-exports in declaration order; first match wins.
      // Resolution must be deterministic (no flaky picks).
      const c = file('c', [def('def:c.X', 'Class', 'c.X')]);
      const d = file('d', [def('def:d.X', 'Class', 'd.X')]);
      const b = file('b', [], [reexport('X', 'X', 'c'), reexport('X', 'X', 'd')]);
      const a = file('a', [], [named('X', 'X', 'b')]);
      const files = [a, b, c, d];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.linkStatus).toBeUndefined();
      // First re-export draft (`from 'c'`) wins. Recording this as the
      // contract — if the algorithm changes to last-wins or merge, this
      // test must be updated alongside the multi-binding propagation
      // pass that mirrors typeBindings (which also uses first-wins).
      expect(edge.targetDefId).toBe('def:c.X');
    });

    it('keeps first-wins precedence stable through cyclic shadowing', () => {
      const c = file('c', [def('def:c.X', 'Class', 'c.X')]);
      const d = file('d', [def('def:d.X', 'Class', 'd.X')]);
      const a = file('a', [], [reexport('X', 'X', 'b'), reexport('X', 'X', 'd')]);
      const b = file('b', [], [reexport('X', 'X', 'a'), reexport('X', 'X', 'c')]);
      const consumer = file('consumer', [], [named('X', 'X', 'a')]);
      const files = [consumer, a, b, c, d];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));

      const edge = firstImport(out, consumer.moduleScope)!;
      expect(edge.linkStatus).toBeUndefined();
      expect(edge.targetDefId).toBe('def:c.X');
      expect(edge.transitiveVia).toEqual(['a', 'b', 'c']);
    });
  });

  describe('aliased + namespace imports', () => {
    it('resolves an alias under its local name while preserving targetExportedName', () => {
      const b = file('b', [def('def:b.User', 'Class', 'b.User')]);
      const a = file('a', [], [aliased('Account', 'User', 'Account', 'b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.kind).toBe('alias');
      expect(edge.localName).toBe('Account');
      expect(edge.targetExportedName).toBe('User');
      expect(edge.targetDefId).toBe('def:b.User');
    });

    it('records namespace imports with origin=namespace in bindings', () => {
      // Provider emits a synthetic module-representing def so the namespace
      // binding can anchor to a real SymbolDefinition.
      const numpyFile = file('numpy.py', [
        def('def:numpy', 'Namespace', 'numpy'),
        def('def:numpy.array', 'Function', 'numpy.array'),
      ]);
      const a = file('a', [], [namespace('np', 'numpy', 'numpy.py')]);
      const files = [a, numpyFile];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const npEdge = firstImport(out, a.moduleScope)!;
      expect(npEdge.kind).toBe('namespace');
      expect(npEdge.targetModuleScope).toBe(numpyFile.moduleScope);

      const bindings = bindingsFor(out, a.moduleScope, 'np');
      expect(bindings.some((b) => b.origin === 'namespace')).toBe(true);
      expect(bindings.find((b) => b.origin === 'namespace')!.def.nodeId).toBe('def:numpy');
    });

    it('links a namespace import to the module scope even when no module-def exists', () => {
      // No synthetic def in target — the edge still resolves to the module
      // scope, just without a `targetDefId`. Bindings materialization skips
      // the binding (no def to anchor to), but the edge itself is linked.
      const numpyFile = file('numpy.py', [def('def:numpy.array', 'Function', 'numpy.array')]);
      const a = file('a', [], [namespace('np', 'numpy', 'numpy.py')]);
      const files = [a, numpyFile];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const npEdge = firstImport(out, a.moduleScope)!;
      expect(npEdge.kind).toBe('namespace');
      expect(npEdge.linkStatus).toBeUndefined();
      expect(npEdge.targetModuleScope).toBe(numpyFile.moduleScope);
      expect(npEdge.targetDefId).toBeUndefined();
    });
  });

  describe('module-scope binding materialization', () => {
    it('lays down local defs with origin=local', () => {
      const a = file('a', [def('def:a.X', 'Class', 'a.X')]);
      const out = finalize({ files: [a], workspaceIndex: undefined }, defaultHooks([a]));
      const bindings = bindingsFor(out, a.moduleScope, 'X');
      expect(bindings.length).toBe(1);
      expect(bindings[0]!.origin).toBe('local');
      expect(bindings[0]!.def.nodeId).toBe('def:a.X');
    });

    it('layers imports on top of local defs via mergeBindings', () => {
      const b = file('b', [def('def:b.User', 'Class', 'b.User')]);
      const a = file('a', [def('def:a.User', 'Class', 'a.User')], [named('User', 'User', 'b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const bindings = bindingsFor(out, a.moduleScope, 'User');
      expect(bindings.length).toBe(2);
      expect(bindings.some((br) => br.origin === 'local')).toBe(true);
      expect(bindings.some((br) => br.origin === 'import')).toBe(true);
    });

    it('resolves imported defs across many files via O(1) defById index lookup', () => {
      // Regression for the materializeBindings O(N²) → O(1) fix:
      // a single consumer importing one symbol from each of N other
      // files must materialize an `import` binding for each. Prior to
      // the fix, finding `def.X` for each edge meant re-scanning every
      // file's localDefs (O(N × D × E)). With the index, every
      // `defById.get` is O(1), so this test stays under 50 ms even
      // at N=200.
      const N = 200;
      const leafFiles: FinalizeFile[] = [];
      const imports: ParsedImport[] = [];
      for (let i = 0; i < N; i++) {
        const fp = `leaf${i}`;
        const localName = `Leaf${i}`;
        leafFiles.push(file(fp, [def(`def:${fp}.${localName}`, 'Class', `${fp}.${localName}`)]));
        imports.push(named(localName, localName, fp));
      }
      const consumer = file('consumer', [], imports);
      const files = [consumer, ...leafFiles];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      for (let i = 0; i < N; i++) {
        const bindings = bindingsFor(out, consumer.moduleScope, `Leaf${i}`);
        expect(bindings.length).toBe(1);
        expect(bindings[0]!.origin).toBe('import');
        expect(bindings[0]!.def.nodeId).toBe(`def:leaf${i}.Leaf${i}`);
      }
    });

    it('honors provider precedence: mergeBindings can drop existing bindings', () => {
      // Provider decides imports win over locals (Python-ish precedence).
      const b = file('b', [def('def:b.User', 'Class', 'b.User')]);
      const a = file('a', [def('def:a.User', 'Class', 'a.User')], [named('User', 'User', 'b')]);
      const files = [a, b];
      const hooks: FinalizeHooks = {
        ...defaultHooks(files),
        mergeBindings(_existing, incoming) {
          // Replace existing with incoming — last-write-wins across tiers.
          return incoming;
        },
      };
      const out = finalize({ files, workspaceIndex: undefined }, hooks);
      const bindings = bindingsFor(out, a.moduleScope, 'User');
      // Only the last merged layer (the import) remains.
      expect(bindings.length).toBe(1);
      expect(bindings[0]!.origin).toBe('import');
    });
  });

  /**
   * `typeOnly` is the one `ParsedImport` fact `check --cycles` needs that
   * finalize cannot re-derive: the emitted `kind` for `import type { X }` is
   * the same `named` a value import produces. So it has to be carried, and
   * carried onto `base` specifically — every finalized edge is built by
   * spreading `base`, including the re-export and namespace paths.
   */
  describe('type-only carry-through', () => {
    const typeNamed = (localName: string, importedName: string, targetRaw: string): ParsedImport =>
      ({ ...named(localName, importedName, targetRaw), typeOnly: true }) as ParsedImport;

    it('carries `typeOnly` onto a linked edge', () => {
      const b = file('b', [def('def:b.User', 'Class', 'b.User')]);
      const a = file('a', [], [typeNamed('User', 'User', 'b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      // Same kind as the value import — which is exactly why the flag exists.
      expect(edge.kind).toBe('named');
      expect(edge.targetDefId).toBe('def:b.User');
      expect(edge.typeOnly).toBe(true);
    });

    it('a value import gets NO `typeOnly` property', () => {
      // Absent, not `false`: the field is spread in only when set, so an
      // ordinary edge keeps the property set it had before this existed.
      const b = file('b', [def('def:b.User', 'Class', 'b.User')]);
      const a = file('a', [], [named('User', 'User', 'b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      expect(firstImport(out, a.moduleScope)!).not.toHaveProperty('typeOnly');
    });

    it('survives an unresolved target', () => {
      // The unresolved branch builds its own `base`; it must set the flag too,
      // or a package-external `import type` would read as a value import if it
      // ever became resolvable.
      const a = file('a', [], [typeNamed('User', 'User', 'external-pkg')]);
      const out = finalize({ files: [a], workspaceIndex: undefined }, defaultHooks([a]));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.linkStatus).toBe('unresolved');
      expect(edge.typeOnly).toBe(true);
    });

    it('survives a re-export hop', () => {
      // `export type { X } from './y'` in a barrel, imported through it. The
      // finalized edge here is built on a later spread of `base`, not the one
      // `makeEdgeDrafts` returned.
      const leaf = file('leaf', [def('def:leaf.User', 'Class', 'leaf.User')]);
      const barrel = file('barrel', [], [reexport('User', 'User', 'leaf')]);
      const a = file('a', [], [typeNamed('User', 'User', 'barrel')]);
      const files = [a, barrel, leaf];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edge = firstImport(out, a.moduleScope)!;
      expect(edge.targetDefId).toBe('def:leaf.User');
      expect(edge.typeOnly).toBe(true);
    });

    it('a kind with no erased spelling never gains the flag', () => {
      const b = file('b', [def('def:b.User', 'Class', 'b.User')]);
      const a = file('a', [], [sideEffect('b'), dynamicResolved('b'), wildcard('b')]);
      const files = [a, b];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      const edges = out.imports.get(a.moduleScope) ?? [];
      expect(edges.length).toBeGreaterThan(0);
      expect(edges.filter((e) => 'typeOnly' in e)).toEqual([]);
    });
  });

  describe('SCC-DAG exposure for parallelism', () => {
    it('returns SCCs in reverse-topological order (leaves first)', () => {
      // c ← b ← a (a imports b, b imports c, c has no imports)
      const c = file('c', [def('def:c.C', 'Class', 'c.C')]);
      const b = file('b', [def('def:b.B', 'Class', 'b.B')], [named('C', 'C', 'c')]);
      const a = file('a', [def('def:a.A', 'Class', 'a.A')], [named('B', 'B', 'b')]);
      const files = [a, b, c];
      const out = finalize({ files, workspaceIndex: undefined }, defaultHooks(files));
      // First SCC processed must be `c` (leaf), last must be `a`.
      expect(out.sccs[0]!.files[0]).toBe('c');
      expect(out.sccs[out.sccs.length - 1]!.files[0]).toBe('a');
    });
  });
});