package unit;

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

/**
 * JenkinsDependencyGraphTest
 *
 * Models two CWE-407 defects in Jenkins:
 *
 * jenkins-0001: DependencyGraph.add()
 *   Defective: iterates List<DependencyGroup> to find an existing edge between two
 *              projects — O(E) per addDependency call → O(E²) total for a dense graph.
 *   Fixed:     forwardIndex/backwardIndex HashMap gives O(1) edge lookup per call.
 *
 * jenkins-0002: AbstractProject.getBuildTriggerUpstreamProjects()
 *   Defective: buildTrigger.getChildJobs(ap) returns a List<Job>; .contains(this)
 *              is O(D) per upstream project → O(U×D) total where U=upstream count,
 *              D=avg downstream fan-out.
 *   Fixed:     convert the child-jobs list to a HashSet once per upstream project
 *              giving O(D) set construction + O(1) lookup.
 *
 * Operation counts are instrumented explicitly — no wall-clock timing — to isolate
 * the algorithmic difference.
 */
public class JenkinsDependencyGraphTest {

    // =========================================================================
    // Models for jenkins-0001: edge-existence lookup in DependencyGraph.add()
    // =========================================================================

    /** A directed edge (upstream → downstream). */
    static class Edge {
        final int upstream;
        final int downstream;
        Edge(int u, int d) { this.upstream = u; this.downstream = d; }
    }

    /**
     * Defective add(): the DependencyGroup list is scanned linearly to find an
     * existing edge for the same (upstream, downstream) pair.
     *
     * Returns the total number of element comparisons performed.
     */
    static long defectiveAddEdges(int[][] pairs) {
        // key = upstream project id → list of (downstream, group-representative-edge)
        Map<Integer, List<Edge>> forward = new HashMap<>();
        long comparisons = 0;

        for (int[] pair : pairs) {
            int upstream   = pair[0];
            int downstream = pair[1];

            List<Edge> list = forward.computeIfAbsent(upstream, k -> new ArrayList<>());
            boolean found = false;
            for (Edge e : list) {
                comparisons++;
                if (e.upstream == upstream && e.downstream == downstream) {
                    // merge — edge already exists, nothing new to add
                    found = true;
                    break;
                }
            }
            if (!found) {
                list.add(new Edge(upstream, downstream));
            }
        }
        return comparisons;
    }

    /**
     * Fixed add(): an index map (upstream → (downstream → group)) provides O(1)
     * lookup, replacing the linear scan.
     *
     * Returns the total number of map get() calls performed (each is O(1)).
     */
    static long fixedAddEdges(int[][] pairs) {
        Map<Integer, List<Edge>> forward    = new HashMap<>();
        // CWE-407 fix: O(1) index
        Map<Integer, Map<Integer, Edge>> forwardIndex = new HashMap<>();
        long lookups = 0;

        for (int[] pair : pairs) {
            int upstream   = pair[0];
            int downstream = pair[1];

            List<Edge>             list  = forward.computeIfAbsent(upstream, k -> new ArrayList<>());
            Map<Integer, Edge>     index = forwardIndex.computeIfAbsent(upstream, k -> new HashMap<>());

            lookups++;  // one O(1) map get per call
            Edge existing = index.get(downstream);
            if (existing != null) {
                // merge — already exists
            } else {
                Edge dg = new Edge(upstream, downstream);
                list.add(dg);
                index.put(downstream, dg);
            }
        }
        return lookups;
    }

    /** Build a pair array: N projects each with D outgoing edges (all distinct). */
    static int[][] makeUniquePairs(int projects, int edgesPerProject) {
        int total = projects * edgesPerProject;
        int[][] pairs = new int[total][2];
        int idx = 0;
        for (int u = 0; u < projects; u++) {
            for (int d = 0; d < edgesPerProject; d++) {
                pairs[idx][0] = u;
                pairs[idx][1] = edgesPerProject * projects + u * edgesPerProject + d; // unique downstream ids
                idx++;
            }
        }
        return pairs;
    }

    /**
     * Build a pair array where the same E edges are submitted R times each,
     * exercising the "already exists" branch on every repeat.
     */
    static int[][] makeRepeatedPairs(int projects, int edgesPerProject, int repeats) {
        int base = projects * edgesPerProject;
        int[][] pairs = new int[base * repeats][2];
        int idx = 0;
        for (int r = 0; r < repeats; r++) {
            for (int u = 0; u < projects; u++) {
                for (int d = 0; d < edgesPerProject; d++) {
                    pairs[idx][0] = u;
                    pairs[idx][1] = edgesPerProject * projects + u * edgesPerProject + d;
                    idx++;
                }
            }
        }
        return pairs;
    }

    // =========================================================================
    // Models for jenkins-0002: List.contains vs Set.contains in child-job lookup
    // =========================================================================

    /**
     * Defective getBuildTriggerUpstreamProjects():
     * For each upstream project, call childJobs.contains(target) on an ArrayList.
     *
     * Returns total comparisons across all upstream projects.
     *
     * @param upstreamCount   number of upstream projects (U)
     * @param childJobsPerUpstream  child-job fan-out per upstream (D)
     * @param targetIndex     index of the target job in the child-jobs list (-1 = absent)
     */
    static long defectiveChildJobLookup(int upstreamCount, int childJobsPerUpstream, int targetIndex) {
        long comparisons = 0;
        for (int u = 0; u < upstreamCount; u++) {
            // getChildJobs(ap) → ArrayList of size childJobsPerUpstream
            // .contains(this) → linear scan
            if (targetIndex < 0) {
                // target absent: scan full list
                comparisons += childJobsPerUpstream;
            } else {
                // target at targetIndex: scan up to and including targetIndex
                comparisons += targetIndex + 1;
            }
        }
        return comparisons;
    }

    /**
     * Fixed getBuildTriggerUpstreamProjects():
     * For each upstream project, build a HashSet from childJobs once, then .contains().
     *
     * Returns total element insertions (O(D) per upstream) — the set construction cost.
     * The lookup itself is O(1) and not counted separately.
     */
    static long fixedChildJobLookup(int upstreamCount, int childJobsPerUpstream) {
        long insertions = 0;
        for (int u = 0; u < upstreamCount; u++) {
            // new HashSet<>(childJobs) — O(D) set construction
            insertions += childJobsPerUpstream;
            // .contains(this) — O(1), not counted
        }
        return insertions;
    }

    // =========================================================================
    // Test 1 — jenkins-0001: single project, many repeated edges
    //          defect performs O(E) scan per repeat; fixed performs O(1)
    // =========================================================================

    static void test1_repeatedEdgesDefectVsFixed() {
        int projects = 1;
        int edgesPerProject = 50;
        int repeats = 10;

        int[][] pairs = makeRepeatedPairs(projects, edgesPerProject, repeats);
        long defectOps = defectiveAddEdges(pairs);
        long fixedOps  = fixedAddEdges(pairs);

        System.out.printf(
            "test1: projects=%d edges=%d repeats=%d  defect_comparisons=%d  fixed_lookups=%d%n",
            projects, edgesPerProject, repeats, defectOps, fixedOps);

        // After the first pass (50 unique edges inserted), each repeat of an existing
        // edge scans the entire list (50 items) before confirming presence.
        // Total comparisons ≥ (repeats-1) * edges * edges (undercount since list grows
        // to full size during first pass) — conservative lower bound:
        long lowerBound = (long)(repeats - 1) * edgesPerProject * (edgesPerProject / 2);
        assert defectOps >= lowerBound
            : "defect comparisons=" + defectOps + " expected >= " + lowerBound;
        assert fixedOps < defectOps
            : "fixed must do fewer operations than defect";
    }

    // =========================================================================
    // Test 2 — jenkins-0001: scaling — doubling edge count grows defect super-linearly
    // =========================================================================

    static void test2_edgeCountScalingDefect() {
        int projects = 1;
        int edges1 = 40;
        int edges2 = 80;
        int repeats = 5;

        long d1 = defectiveAddEdges(makeRepeatedPairs(projects, edges1, repeats));
        long d2 = defectiveAddEdges(makeRepeatedPairs(projects, edges2, repeats));
        long f1 = fixedAddEdges(makeRepeatedPairs(projects, edges1, repeats));
        long f2 = fixedAddEdges(makeRepeatedPairs(projects, edges2, repeats));

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

        System.out.printf(
            "test2: defect_growth=%.2fx (edges 2x)  fixed_growth=%.2fx%n",
            defectGrowth, fixedGrowth);

        // Defect is quadratic in E: doubling edges should more than double comparisons
        assert defectGrowth > 2.0
            : "defect should grow super-linearly, got " + defectGrowth;
        // Fixed is linear in E: doubling edges ≤ 2.5x (hash overhead margin)
        assert fixedGrowth <= 2.5
            : "fixed should grow at most linearly, got " + fixedGrowth;
        assert defectGrowth > fixedGrowth
            : "defect growth must exceed fixed growth";
    }

    // =========================================================================
    // Test 3 — jenkins-0001: unique edges only (no repeats, insert-only path)
    //          both implementations do linear work; defect still scans existing
    //          entries before inserting each new edge
    // =========================================================================

    static void test3_uniqueEdgesOnlyComparisonCount() {
        int projects = 1;
        int edgesPerProject = 100;

        int[][] pairs = makeUniquePairs(projects, edgesPerProject);
        long defectOps = defectiveAddEdges(pairs);
        long fixedOps  = fixedAddEdges(pairs);

        // Defect: inserting edge i requires scanning i existing edges → 0+1+2+…+(E-1) = E*(E-1)/2
        long expectedDefect = (long) edgesPerProject * (edgesPerProject - 1) / 2;
        // Fixed: E lookups (one get() per edge, always misses for unique set)
        long expectedFixed  = edgesPerProject;

        System.out.printf(
            "test3: unique_edges=%d  defect=%d (expect=%d)  fixed=%d (expect=%d)%n",
            edgesPerProject, defectOps, expectedDefect, fixedOps, expectedFixed);

        assert defectOps == expectedDefect
            : "defect comparisons=" + defectOps + " expected=" + expectedDefect;
        assert fixedOps == expectedFixed
            : "fixed lookups=" + fixedOps + " expected=" + expectedFixed;
    }

    // =========================================================================
    // Test 4 — jenkins-0002: target absent from child-job list
    //          defect scans full D-length list per upstream; fixed builds set + O(1)
    // =========================================================================

    static void test4_childJobLookupTargetAbsent() {
        int upstreamCount       = 50;
        int childJobsPerUpstream = 80;

        long defectOps = defectiveChildJobLookup(upstreamCount, childJobsPerUpstream, -1);
        long fixedOps  = fixedChildJobLookup(upstreamCount, childJobsPerUpstream);

        // Defect: U × D comparisons (target absent → full list scanned every time)
        long expectedDefect = (long) upstreamCount * childJobsPerUpstream;
        // Fixed: U × D insertions (set construction), but lookup is O(1)
        long expectedFixed  = (long) upstreamCount * childJobsPerUpstream;

        System.out.printf(
            "test4: upstream=%d child_jobs=%d  defect_comparisons=%d  fixed_insertions=%d%n",
            upstreamCount, childJobsPerUpstream, defectOps, fixedOps);

        assert defectOps == expectedDefect
            : "defect=" + defectOps + " expected=" + expectedDefect;
        assert fixedOps == expectedFixed
            : "fixed=" + fixedOps + " expected=" + expectedFixed;
        // Both are O(U×D) for construction; but defect's .contains is an additional O(D)
        // per call that the fix eliminates. The assert below verifies equal cost at this
        // abstraction level; the advantage comes from subsequent repeated lookups.
        assert defectOps >= fixedOps
            : "defect should be at least as expensive as fixed construction cost";
    }

    // =========================================================================
    // Test 5 — jenkins-0002: scaling upstream count
    //          defect cost grows as O(U×D); verify linear growth with U
    // =========================================================================

    static void test5_childJobLookupScaling() {
        int childJobsPerUpstream = 60;
        int upstream1 = 50;
        int upstream2 = 100; // 2x upstream

        long d1 = defectiveChildJobLookup(upstream1, childJobsPerUpstream, -1);
        long d2 = defectiveChildJobLookup(upstream2, childJobsPerUpstream, -1);
        long f1 = fixedChildJobLookup(upstream1, childJobsPerUpstream);
        long f2 = fixedChildJobLookup(upstream2, childJobsPerUpstream);

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

        System.out.printf(
            "test5: child_jobs=%d  defect_growth=%.2fx (upstream 2x)  fixed_growth=%.2fx%n",
            childJobsPerUpstream, defectGrowth, fixedGrowth);

        // Both grow linearly with U here (O(U×D)); the fix advantage is the O(1) per-lookup
        // vs O(D) for List.contains — captured when D is large and many lookups occur.
        assert Math.abs(defectGrowth - 2.0) < 0.1
            : "defect should grow exactly 2x with 2x upstream, got " + defectGrowth;
        assert Math.abs(fixedGrowth - 2.0) < 0.1
            : "fixed should grow exactly 2x with 2x upstream, got " + fixedGrowth;

        // Verify absolute counts match O(U×D) formula
        assert d1 == (long) upstream1 * childJobsPerUpstream
            : "defect d1=" + d1 + " expected=" + (upstream1 * childJobsPerUpstream);
        assert f2 == (long) upstream2 * childJobsPerUpstream
            : "fixed f2=" + f2 + " expected=" + (upstream2 * childJobsPerUpstream);
    }

    // =========================================================================
    // Main
    // =========================================================================

    public static void main(String[] args) {
        System.out.println("=== JenkinsDependencyGraphTest ===");
        System.out.println("Modelling CWE-407 defects:");
        System.out.println("  jenkins-0001: DependencyGraph.add() O(E) list scan → O(1) HashMap index");
        System.out.println("  jenkins-0002: getBuildTriggerUpstreamProjects() List.contains → HashSet");
        System.out.println();

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

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

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

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

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

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