package unit;

import java.util.*;

/**
 * julia-0002: Julia Compiler reinfer.jl visited Method[] O(V²) → Set O(V)
 *
 * In Compiler/src/reinfer.jl (method interference BFS):
 *
 *   visited = Method[]         # Array — O(V) membership
 *   push!(visited, method2)
 *   while !isempty(workqueue)
 *       method3 in visited && continue   # O(V) per check — CWE-407
 *       push!(visited, method3)
 *
 * With V methods in the interference graph, total cost: O(V²).
 * Called during type inference for every ambiguous method pair.
 *
 * Fix: visited = Set{Method}() — O(1) membership.
 *
 * UNDF: assigned by generate_undf.py
 * Severity: MEDIUM
 */
public class JuliaReinferVisitedTest {

    static long cmpOps = 0;

    // Simulate Julia BFS with visited = Array (slow)
    static int bfsSlow(int[][] adjacency, int start, int total) {
        List<Integer> visited = new ArrayList<>();
        visited.add(start);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        int count = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            count++;
            for (int next : adjacency[curr]) {
                boolean found = false;
                for (int v : visited) {
                    cmpOps++;
                    if (v == next) { found = true; break; }
                }
                if (!found) {
                    visited.add(next);
                    queue.add(next);
                }
            }
        }
        return count;
    }

    // Simulate Julia BFS with visited = Set (fast)
    static int bfsFast(int[][] adjacency, int start, long[] fastOps) {
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        int count = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            count++;
            for (int next : adjacency[curr]) {
                fastOps[0]++;  // O(1) hash lookup
                if (visited.add(next)) {
                    queue.add(next);
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        // Build a method interference graph with V=500 nodes
        // Each method has ~5 neighbors (typical interference fan-out)
        int V = 500;
        int FAN = 5;
        Random rng = new Random(42);
        int[][] adj = new int[V][];
        for (int i = 0; i < V; i++) {
            Set<Integer> nbrs = new LinkedHashSet<>();
            while (nbrs.size() < FAN) nbrs.add(rng.nextInt(V));
            adj[i] = nbrs.stream().mapToInt(x -> x).toArray();
        }

        // SLOW
        cmpOps = 0;
        int slowVisited = bfsSlow(adj, 0, V);

        long slowCmp = cmpOps;

        // FAST
        long[] fastOps = {0};
        int fastVisited = bfsFast(adj, 0, fastOps);

        if (slowVisited != fastVisited) {
            System.err.printf("FAIL: BFS reached slow=%d fast=%d nodes%n", slowVisited, fastVisited);
            System.exit(1);
        }

        double ratio = (double) slowCmp / Math.max(fastOps[0], 1);
        System.out.printf("julia-0002 reinfer BFS: SLOW=%d cmpOps, FAST~=%d ops, ratio=%.1fx%n",
                slowCmp, fastOps[0], ratio);

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