import { describe, expect, it } from "@suaveplan/testing/runner";
import fc from "fast-check";
import { topologicalSort } from "../src/topo-sort/topo-sort.js";
import type { PluginNode } from "../src/types/api-plugin.js";

/** Generate an acyclic dep graph: each node's deps only point to earlier ids. */
const acyclicGraphArb = fc
    .array(fc.string({ minLength: 1, maxLength: 4 }), {
        minLength: 1,
        maxLength: 20,
    })
    .map((rawIds) => {
        const ids = Array.from(new Set(rawIds));
        return ids;
    })
    .filter((ids) => ids.length > 0)
    .chain((ids) =>
        fc
            .tuple(
                ...ids.map((_, i) =>
                    fc.subarray(ids.slice(0, i), { maxLength: i })
                )
            )
            .map((depsPerNode) =>
                ids.map<PluginNode<null>>((id, i) => ({
                    id,
                    data: null,
                    dependencies: depsPerNode[i] ?? [],
                }))
            )
    );

describe("topologicalSort — property tests", () => {
    it("sorted order satisfies dep invariant", { timeout: 30000 }, () => {
        fc.assert(
            fc.property(acyclicGraphArb, (nodes) => {
                const { sorted } = topologicalSort(nodes);
                const positions = new Map<string, number>();
                sorted.forEach((n, i) => positions.set(n.id, i));
                for (const node of sorted) {
                    for (const dep of node.dependencies) {
                        const depPos = positions.get(dep);
                        const nodePos = positions.get(node.id);
                        // dep must appear before node (if dep is in the graph)
                        if (depPos !== undefined && nodePos !== undefined) {
                            expect(depPos).toBeLessThan(nodePos);
                        }
                    }
                }
            }),
            { numRuns: 200 }
        );
    });

    it("sort is deterministic across repeated calls", {
        timeout: 30000,
    }, () => {
        fc.assert(
            fc.property(acyclicGraphArb, (nodes) => {
                const a = topologicalSort(nodes).sorted.map((n) => n.id);
                const b = topologicalSort(nodes).sorted.map((n) => n.id);
                expect(a).toEqual(b);
            }),
            { numRuns: 200 }
        );
    });
});