package unit;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * AnsibleRoleTest
 *
 * Models three CWE-407 defects in ansible/ansible:
 *
 *   ANS-001 (MEDIUM) — get_vars(): `seen = []` list deduplication over transitive
 *     dependencies.  Each `dep not in seen` is O(D) → O(D^2) total.
 *     Fix: identity-keyed set — `seen_ids = set()` with id(dep), O(1) per check.
 *
 *   ANS-002 (LOW) — _load_role_data(): `self.collections` list membership tests.
 *     `c not in self.collections` is O(C) per candidate; two further
 *     `not in self.collections` guards add O(C) each → O(C) total per call.
 *     Fix: parallel _collections_set for O(1) membership.
 *
 *   PUP-001 (LOW, error path) — paths_in_cycle() BFS: frame[1].member?(frame[0])
 *     where frame[1] is a growing Array.  O(path) per BFS step → O(|cycle|^3)
 *     worst case.  Fix: Set alongside Array for O(1) include?.
 *
 * All measurements are instrumented operation counts, not wall-clock timing.
 */
public class AnsibleRoleTest {

    // -----------------------------------------------------------------------
    // ANS-001 modelling helpers
    // Defective: ArrayList.contains() — O(D) linear scan per dep
    // Fixed:     HashMap keyed by identity integer — O(1) containsKey
    // -----------------------------------------------------------------------

    /** Returns total contains-calls performed (each call costs 1 unit). */
    static long ans001Defective(int[] depIds) {
        ArrayList<Integer> seen = new ArrayList<>();
        long comparisons = 0;
        for (int dep : depIds) {
            // model `dep not in seen` — O(current seen size)
            comparisons += seen.size();   // worst-case linear scan cost
            if (!seen.contains(dep)) {
                seen.add(dep);
            }
        }
        return comparisons;
    }

    /** Returns total lookup-calls performed (each O(1) hash lookup costs 1 unit). */
    static long ans001Fixed(int[] depIds) {
        HashMap<Integer, Boolean> seenIds = new HashMap<>();
        long lookups = 0;
        for (int dep : depIds) {
            lookups++;                    // one O(1) hash lookup per dep
            if (!seenIds.containsKey(dep)) {
                seenIds.put(dep, Boolean.TRUE);
            }
        }
        return lookups;
    }

    // -----------------------------------------------------------------------
    // ANS-002 modelling helpers
    // Defective: ArrayList membership for each candidate collection
    // Fixed:     HashSet membership — O(1)
    // -----------------------------------------------------------------------

    static long ans002Defective(String[] candidates, String[] existing) {
        ArrayList<String> collections = new ArrayList<>();
        for (String e : existing) collections.add(e);

        long scans = 0;
        for (String c : candidates) {
            // model `c not in self.collections` — O(C) per candidate
            scans += collections.size();
            if (!collections.contains(c)) {
                collections.add(c);
            }
        }
        // model two sentinel checks: 'ansible.builtin' not in and 'ansible.legacy' not in
        scans += collections.size(); // builtin check
        scans += collections.size(); // legacy check
        return scans;
    }

    static long ans002Fixed(String[] candidates, String[] existing) {
        ArrayList<String> collections = new ArrayList<>();
        HashSet<String> collectionsSet = new HashSet<>();
        for (String e : existing) {
            collections.add(e);
            collectionsSet.add(e);
        }

        long lookups = 0;
        for (String c : candidates) {
            lookups++;               // O(1) set lookup per candidate
            if (!collectionsSet.contains(c)) {
                collections.add(c);
                collectionsSet.add(c);
            }
        }
        lookups++;  // builtin check — O(1)
        lookups++;  // legacy check — O(1)
        return lookups;
    }

    // -----------------------------------------------------------------------
    // PUP-001 modelling helpers
    // Models BFS over a cycle of length N; each BFS step tests membership of
    // the current vertex in the current path.
    //
    // Defective: path is ArrayList; path.contains() is O(path_length)
    // Fixed:     path membership via HashSet; O(1) contains
    //
    // Returns total membership-test cost across all BFS steps.
    // -----------------------------------------------------------------------

    static long pup001Defective(int cycleLen) {
        // Each vertex has exactly one successor in a simple cycle: v -> (v+1) % N
        // BFS starting from vertex 0; path grows until we revisit a vertex.
        // We simulate the BFS and count the cost of each ArrayList.contains call.
        long cost = 0;

        // BFS frame: [vertex, path as ArrayList]
        // Use a simple ArrayList-of-ArrayLists to model the stack
        ArrayList<Object[]> stack = new ArrayList<>();
        ArrayList<Integer> initPath = new ArrayList<>();
        stack.add(new Object[]{0, initPath});

        int steps = 0;
        while (!stack.isEmpty() && steps < cycleLen * cycleLen * 4) {
            Object[] frame = stack.remove(0);
            int vertex = (Integer) frame[0];
            @SuppressWarnings("unchecked")
            ArrayList<Integer> path = (ArrayList<Integer>) frame[1];

            // model frame[1].member?(frame[0]) — O(path.size())
            cost += path.size();   // cost of linear scan

            if (path.contains(vertex)) {
                // cycle found — stop this branch
            } else {
                ArrayList<Integer> newPath = new ArrayList<>(path);
                newPath.add(vertex);
                int next = (vertex + 1) % cycleLen;
                stack.add(new Object[]{next, newPath});
            }
            steps++;
        }
        return cost;
    }

    static long pup001Fixed(int cycleLen) {
        long cost = 0;

        // BFS frame: [vertex, path ArrayList, path HashSet]
        ArrayList<Object[]> stack = new ArrayList<>();
        ArrayList<Integer> initPath = new ArrayList<>();
        HashSet<Integer> initSet = new HashSet<>();
        stack.add(new Object[]{0, initPath, initSet});

        int steps = 0;
        while (!stack.isEmpty() && steps < cycleLen * cycleLen * 4) {
            Object[] frame = stack.remove(0);
            int vertex = (Integer) frame[0];
            @SuppressWarnings("unchecked")
            ArrayList<Integer> path = (ArrayList<Integer>) frame[1];
            @SuppressWarnings("unchecked")
            HashSet<Integer> pathSet = (HashSet<Integer>) frame[2];

            // model path_set.include?(vertex) — O(1)
            cost += 1;   // one hash lookup

            if (pathSet.contains(vertex)) {
                // cycle found — stop this branch
            } else {
                ArrayList<Integer> newPath = new ArrayList<>(path);
                newPath.add(vertex);
                HashSet<Integer> newSet = new HashSet<>(pathSet);
                newSet.add(vertex);
                int next = (vertex + 1) % cycleLen;
                stack.add(new Object[]{next, newPath, newSet});
            }
            steps++;
        }
        return cost;
    }

    // -----------------------------------------------------------------------
    // Test 1 — ANS-001: defective O(D^2) vs fixed O(D) at D=60 unique deps
    // -----------------------------------------------------------------------

    static void test1_ans001_quadraticVsLinear() {
        int D = 60;
        int[] depIds = new int[D];
        for (int i = 0; i < D; i++) depIds[i] = i;  // all unique

        long defectCost = ans001Defective(depIds);
        long fixedCost  = ans001Fixed(depIds);

        System.out.printf("test1 ANS-001: D=%d unique  defect=%d  fixed=%d%n",
                D, defectCost, fixedCost);

        assert defectCost > fixedCost
                : "defect must be more expensive than fix at D=" + D;
        // defective scans: 0+1+2+...+(D-1) = D*(D-1)/2
        long expectedDefect = (long) D * (D - 1) / 2;
        assert defectCost == expectedDefect
                : "expected defect cost=" + expectedDefect + " got=" + defectCost;
        double ratio = (double) defectCost / Math.max(1, fixedCost);
        assert ratio > 10.0
                : "expected ratio>10x for D=" + D + ", got " + ratio;
    }

    // -----------------------------------------------------------------------
    // Test 2 — ANS-001: duplicate deps case — defect still O(D^2), fix O(D)
    // -----------------------------------------------------------------------

    static void test2_ans001_duplicateDeps() {
        int D = 80;
        // half-unique: dep IDs repeat every D/2 values → many duplicates
        int[] depIds = new int[D];
        int half = D / 2;
        for (int i = 0; i < D; i++) depIds[i] = i % half;

        long defectCost = ans001Defective(depIds);
        long fixedCost  = ans001Fixed(depIds);

        double ratio = (double) defectCost / Math.max(1, fixedCost);
        System.out.printf("test2 ANS-001: D=%d half-unique  defect=%d  fixed=%d  ratio=%.1fx%n",
                D, defectCost, fixedCost, ratio);

        assert defectCost > fixedCost
                : "defect must be more expensive than fix at D=" + D + " with duplicates";
        assert ratio > 5.0
                : "expected ratio>5x for half-unique D=" + D + ", got " + ratio;
    }

    // -----------------------------------------------------------------------
    // Test 3 — ANS-002: collections list membership — defect O(C^2), fix O(C)
    // -----------------------------------------------------------------------

    static void test3_ans002_collectionsSet() {
        int C = 50;
        String[] existing = new String[5];
        for (int i = 0; i < 5; i++) existing[i] = "existing.collection." + i;

        String[] candidates = new String[C];
        for (int i = 0; i < C; i++) candidates[i] = "meta.collection." + i;

        long defectCost = ans002Defective(candidates, existing);
        long fixedCost  = ans002Fixed(candidates, existing);

        double ratio = (double) defectCost / Math.max(1, fixedCost);
        System.out.printf("test3 ANS-002: C=%d candidates  defect=%d  fixed=%d  ratio=%.1fx%n",
                C, defectCost, fixedCost, ratio);

        assert defectCost > fixedCost
                : "defect must be more expensive than fix for C=" + C + " collections";
        assert ratio > 5.0
                : "expected ratio>5x, got " + ratio;
    }

    // -----------------------------------------------------------------------
    // Test 4 — PUP-001: BFS path membership — defect O(N^3), fix O(N)
    //          Cycle length N=20 — defect accumulates scan cost, fix stays O(N)
    // -----------------------------------------------------------------------

    static void test4_pup001_pathMembershipSet() {
        int N = 20;
        long defectCost = pup001Defective(N);
        long fixedCost  = pup001Fixed(N);

        double ratio = (double) defectCost / Math.max(1, fixedCost);
        System.out.printf("test4 PUP-001: cycle_len=%d  defect=%d  fixed=%d  ratio=%.1fx%n",
                N, defectCost, fixedCost, ratio);

        assert defectCost > fixedCost
                : "defect must be more expensive than fix at cycle_len=" + N;
        assert ratio > 3.0
                : "expected ratio>3x, got " + ratio;
    }

    // -----------------------------------------------------------------------
    // Test 5 — PUP-001: scaling — doubling cycle length grows defect faster
    //          than fixed, demonstrating super-linear vs linear growth
    // -----------------------------------------------------------------------

    static void test5_pup001_scalingGrowth() {
        int N1 = 15;
        int N2 = 30;  // double cycle length

        long d1 = pup001Defective(N1);
        long d2 = pup001Defective(N2);
        long f1 = pup001Fixed(N1);
        long f2 = pup001Fixed(N2);

        double defectGrowth = (double) d2 / Math.max(1, d1);
        double fixedGrowth  = (double) f2 / Math.max(1, f1);

        System.out.printf("test5 PUP-001: N1=%d N2=%d  defect_growth=%.2fx  fixed_growth=%.2fx%n",
                N1, N2, defectGrowth, fixedGrowth);

        assert defectGrowth > fixedGrowth
                : "defect should grow faster than fix when cycle doubles; defect=" + defectGrowth + " fixed=" + fixedGrowth;
        assert defectGrowth > 2.0
                : "defect should grow super-linearly (>2x) when N doubles, got " + defectGrowth;
        assert fixedGrowth <= 3.0
                : "fixed should grow at most linearly (~2x) when N doubles, got " + fixedGrowth;
    }

    // -----------------------------------------------------------------------
    // Main
    // -----------------------------------------------------------------------

    public static void main(String[] args) {
        System.out.println("=== AnsibleRoleTest ===");
        System.out.println("Modelling CWE-407: ANS-001 get_vars seen-list, ANS-002 collections-list, PUP-001 BFS path Array");
        System.out.println();

        test1_ans001_quadraticVsLinear();
        System.out.println("  PASS test1_ans001_quadraticVsLinear");

        test2_ans001_duplicateDeps();
        System.out.println("  PASS test2_ans001_duplicateDeps");

        test3_ans002_collectionsSet();
        System.out.println("  PASS test3_ans002_collectionsSet");

        test4_pup001_pathMembershipSet();
        System.out.println("  PASS test4_pup001_pathMembershipSet");

        test5_pup001_scalingGrowth();
        System.out.println("  PASS test5_pup001_scalingGrowth");

        System.out.println();
        System.out.println("All 5 tests PASSED.");
    }
}