package unit;

import java.util.*;

/**
 * spidermonkey-0005: GatherAvailableModuleAncestors O(M²) execList scan
 *
 * In js/src/vm/Modules.cpp GatherAvailableModuleAncestors():
 *
 *   ContainsElement(execList, m)  // O(M) linear scan of growing vector
 *
 * Called recursively over async module graph — execList grows as BFS proceeds.
 * Total cost: O(M × P) where M = modules in execList, P = parent edges.
 *
 * Fix: shadow HashSet<ModuleObject*> for O(1) membership check.
 *
 * UNDF: assigned by generate_undf.py
 * Severity: MEDIUM
 */
public class SpiderMonkeyGatherAncestorsTest {

    static long slowOps = 0;
    static long fastOps = 0;

    /**
     * Simulate GatherAvailableModuleAncestors — SLOW path.
     * execList is a List (vector) — ContainsElement is O(|execList|).
     */
    static void gatherSlow(int[][] parents, int module, List<Integer> execList) {
        for (int parent : parents[module]) {
            // ContainsElement(execList, parent) — O(|execList|) scan
            boolean found = false;
            for (int x : execList) {
                slowOps++;
                if (x == parent) { found = true; break; }
            }
            if (!found) {
                execList.add(parent);
                gatherSlow(parents, parent, execList);
            }
        }
    }

    /**
     * Simulate GatherAvailableModuleAncestors — FAST path.
     * execSet is a HashSet — membership check is O(1).
     */
    static void gatherFast(int[][] parents, int module, List<Integer> execList, Set<Integer> execSet) {
        for (int parent : parents[module]) {
            fastOps++;  // O(1) hash lookup
            if (execSet.add(parent)) {
                execList.add(parent);
                gatherFast(parents, parent, execList, execSet);
            }
        }
    }

    public static void main(String[] args) {
        // Build async module graph:
        // M modules arranged in a diamond-rich DAG.
        // Each module has 3 async parents, creating many shared ancestors.
        int M = 300;
        int FAN = 3;
        Random rng = new Random(12345);

        // parents[i] = list of modules that depend on module i (async parents)
        int[][] parents = new int[M][];
        for (int i = 0; i < M; i++) {
            // Each module has FAN parents from among lower-indexed modules
            // (simulates a layered async module graph)
            Set<Integer> ps = new LinkedHashSet<>();
            if (i > 0) {
                while (ps.size() < Math.min(FAN, i)) {
                    ps.add(rng.nextInt(i));
                }
            }
            parents[i] = ps.stream().mapToInt(x -> x).toArray();
        }

        // Root module triggers the gather from module M-1
        int root = M - 1;

        // SLOW: vector-based execList
        slowOps = 0;
        List<Integer> slowExecList = new ArrayList<>();
        slowExecList.add(root);
        gatherSlow(parents, root, slowExecList);
        long totalSlowOps = slowOps;

        // FAST: hashset-based execSet
        fastOps = 0;
        List<Integer> fastExecList = new ArrayList<>();
        Set<Integer> fastExecSet = new HashSet<>();
        fastExecList.add(root);
        fastExecSet.add(root);
        gatherFast(parents, root, fastExecList, fastExecSet);
        long totalFastOps = fastOps;

        // Both must reach the same set of modules
        Set<Integer> slowSet = new HashSet<>(slowExecList);
        Set<Integer> fastSet = new HashSet<>(fastExecList);
        if (!slowSet.equals(fastSet)) {
            System.err.printf("FAIL: execList mismatch — slow=%d modules, fast=%d modules%n",
                    slowSet.size(), fastSet.size());
            System.exit(1);
        }

        double ratio = (double) totalSlowOps / Math.max(totalFastOps, 1);
        System.out.printf(
            "spidermonkey-0005 GatherAvailableAncestors: SLOW=%d ops, FAST=%d ops, ratio=%.1fx%n",
            totalSlowOps, totalFastOps, ratio);

        if (ratio < 5.0) {
            System.err.printf("FAIL: ratio %.1f < 5x (expected O(M²) vs O(M))%n", ratio);
            System.exit(1);
        }
        System.out.println("PASS");
    }
}