package unit;

import java.util.*;

/**
 * Unit test for nestjs-0001/0002: CWE-407 in NestJS DI scanner.
 *
 * nestjs-0001 (HIGH):
 *   File:   packages/core/scanner.ts:155
 *   Symbol: DependenciesScanner.scanForModules — ctxRegistry.includes(innerModule)
 *   Defect: The module-scan visited-set is a plain Array passed by reference
 *   through all recursive scanForModules() calls. At each module in the import
 *   list, Array.includes() performs an O(n) scan of the ever-growing registry.
 *   For N modules total: sum 0+1+...+(N-1) = N*(N-1)/2 comparisons = O(N²).
 *   Fix:    Replace ctxRegistry: Array with ctxRegistry: Set; use Set.add()
 *   and Set.has() — both O(1). Cold-start speedup is ~N/2 at large N.
 *
 * nestjs-0002 (MEDIUM):
 *   File:   packages/common/module-utils/utils/get-injection-providers.util.ts:41-42
 *   Symbol: getInjectionProviders — result.includes(p), search.includes(p)
 *   Defect: Provider dependency resolution loop uses Array.includes() against
 *   both a growing result accumulator and a search list on every filter call.
 *   With P providers, R result items, S search items, W iterations:
 *   O(P × W × (R + 2S)) comparisons per getInjectionProviders() call.
 *   Fix:    Maintain resultSet: Set<Provider> and searchSet: Set<InjectionToken>
 *   as companions; replace .includes() with .has() — O(1) per check.
 *
 * Modeled here in Java:
 *   JS Array + .includes()  ≡  List<T> + contains()  (defective)
 *   JS Set   + .has()       ≡  java.util.Set + contains()  (fixed)
 *   comparisons tracked at each membership-test site.
 *
 * Expected at N=300 (nestjs-0001): ratio > 50x
 * Expected at nestjs-0002 scale:   ratio > 10x
 */
public class NestJSTest {

    static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
        slow.run(); fast.run();
        long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime()-t0)/1_000_000;
        long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime()-t1)/1_000_000;
        double r = fOps > 0 ? (double)sOps/fOps : 0;
        System.out.printf("  %-52s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.0fx%n",
                label, sMs, sOps, fMs, fOps, r);
    }

    // =========================================================================
    // nestjs-0001 model: ctxRegistry as Array vs Set in recursive module scan
    // =========================================================================

    /**
     * Defective scanForModules: ctxRegistry is a plain List.
     * Simulates visiting N modules in a linear chain: each module imports the
     * next. The registry grows by 1 per visit; at visit k the .contains() scan
     * examines k elements. Total comparisons = 0+1+...+(N-1) = N*(N-1)/2.
     */
    static class DefectiveScanner {
        long comparisons = 0;

        void scan(int moduleId, List<Object> ctxRegistry, int totalModules) {
            Object module = moduleId;
            ctxRegistry.add(module);

            // Simulate one import per module (linear chain)
            if (moduleId + 1 < totalModules) {
                Object nextModule = moduleId + 1;
                // ctxRegistry.includes(nextModule) — O(n) scan
                boolean found = false;
                for (Object m : ctxRegistry) {
                    comparisons++;
                    if (m.equals(nextModule)) { found = true; break; }
                }
                if (!found) {
                    scan(moduleId + 1, ctxRegistry, totalModules);
                }
            }
        }

        void run(int N) {
            List<Object> ctxRegistry = new ArrayList<>();
            scan(0, ctxRegistry, N);
        }
    }

    /**
     * Fixed scanForModules: ctxRegistry is a Set.
     * Set.contains() is O(1) average. Total comparisons = N-1 (one per module
     * after the root, since the root is never checked against itself).
     */
    static class FixedScanner {
        long comparisons = 0;

        void scan(int moduleId, Set<Object> ctxRegistry, int totalModules) {
            Object module = moduleId;
            ctxRegistry.add(module);

            if (moduleId + 1 < totalModules) {
                Object nextModule = moduleId + 1;
                // ctxRegistry.has(nextModule) — O(1)
                comparisons++;
                if (!ctxRegistry.contains(nextModule)) {
                    scan(moduleId + 1, ctxRegistry, totalModules);
                }
            }
        }

        void run(int N) {
            Set<Object> ctxRegistry = new HashSet<>();
            scan(0, ctxRegistry, N);
        }
    }

    // =========================================================================
    // nestjs-0002 model: getInjectionProviders Array.includes vs Set.has
    // =========================================================================

    /**
     * Defective getInjectionProviders: result and search are plain Lists.
     *
     * The key defect: for each of P providers per iteration, the code does
     * result.includes(p) — an O(result.size) scan — and search.includes(p) —
     * an O(search.size) scan. As result accumulates providers over W iterations
     * the result.includes cost dominates.
     *
     * Worst-case model: search is size S each round, all providers match on the
     * first iteration and go into result; subsequent iterations re-scan result
     * for all P providers (finding them all already there, full scans each time).
     */
    static long getInjectionProvidersDefective(int P, int W) {
        long comparisons = 0;
        List<Integer> result = new ArrayList<>();
        // seed result with half of P to simulate partially-filled accumulator
        int preload = P / 2;
        for (int i = 0; i < preload; i++) result.add(i);

        // Each of W iterations: filter all P providers against result (O(result.size))
        int S = 5; // fixed search size
        List<Integer> search = new ArrayList<>();
        for (int i = preload; i < preload + S && i < P; i++) search.add(i);

        for (int iter = 0; iter < W && !search.isEmpty(); iter++) {
            List<Integer> match = new ArrayList<>();
            for (int p = 0; p < P; p++) {
                // result.includes(p) — O(result.size)
                boolean inResult = false;
                for (int r : result) {
                    comparisons++;
                    if (r == p) { inResult = true; break; }
                }
                if (inResult) continue;

                // search.includes(p) — O(search.size)
                boolean inSearch = false;
                for (int s : search) {
                    comparisons++;
                    if (s == p) { inSearch = true; break; }
                }
                if (inSearch) match.add(p);
            }
            result.addAll(match);

            // Advance search window (new deps)
            int base = preload + S + iter * S;
            search = new ArrayList<>();
            for (int i = base; i < base + S && i < P; i++) search.add(i);
        }
        return comparisons;
    }

    /**
     * Fixed getInjectionProviders: result and search backed by Sets.
     * All membership checks are O(1).
     */
    static long getInjectionProvidersFixed(int P, int W) {
        long comparisons = 0;
        List<Integer> result = new ArrayList<>();
        Set<Integer> resultSet = new HashSet<>();
        int preload = P / 2;
        for (int i = 0; i < preload; i++) { result.add(i); resultSet.add(i); }

        int S = 5;
        Set<Integer> searchSet = new HashSet<>();
        for (int i = preload; i < preload + S && i < P; i++) searchSet.add(i);

        for (int iter = 0; iter < W && !searchSet.isEmpty(); iter++) {
            List<Integer> match = new ArrayList<>();
            for (int p = 0; p < P; p++) {
                comparisons++;  // resultSet.has(p) — O(1)
                if (resultSet.contains(p)) continue;
                comparisons++;  // searchSet.has(p) — O(1)
                if (searchSet.contains(p)) match.add(p);
            }
            for (int m : match) { result.add(m); resultSet.add(m); }

            int base = preload + S + iter * S;
            searchSet = new HashSet<>();
            for (int i = base; i < base + S && i < P; i++) searchSet.add(i);
        }
        return comparisons;
    }

    // =========================================================================
    // Tests
    // =========================================================================

    /**
     * Test 1 — Correctness: defective and fixed scanners visit the same modules.
     */
    static void testScannerCorrectnessMatch() {
        int N = 50;
        DefectiveScanner def = new DefectiveScanner();
        FixedScanner     fix = new FixedScanner();

        // Both should visit all N modules (linear chain means all are reachable)
        def.run(N);
        fix.run(N);

        // After visiting N modules comparisons follow:
        // Defective: when visiting module k (0-indexed), registry has size k,
        //   so .contains() on the next module scans k elements.
        //   Total = 1+2+...+(N-1) = N*(N-1)/2
        // Fixed: each visit does exactly 1 Set.contains() for the child check.
        //   Total = N-1 (root has one child check; leaf module has no child)
        long expectedDef = (long) N * (N - 1) / 2;
        assert def.comparisons == expectedDef
            : "defective scanner comparisons should be N*(N-1)/2=" + expectedDef
              + "; got " + def.comparisons;
        assert fix.comparisons == N - 1
            : "fixed scanner comparisons should be N-1=" + (N - 1)
              + "; got " + fix.comparisons;

        System.out.println("PASS testScannerCorrectnessMatch");
    }

    /**
     * Test 2 — nestjs-0001: ratio of defective vs fixed scanner comparisons > 50x at N=300.
     *
     * Defective: (N-1)*(N-2)/2 comparisons ~ O(N²)
     * Fixed:     N-1 comparisons ~ O(N)
     * Ratio at N=300: ~149x
     */
    static void testScannerRatioAtScale() {
        int N = 300;
        DefectiveScanner def = new DefectiveScanner();
        FixedScanner     fix = new FixedScanner();
        def.run(N);
        fix.run(N);

        long defComp = def.comparisons;
        long fixComp = fix.comparisons;
        double ratio = (double) defComp / fixComp;

        long expectedDef = (long) N * (N - 1) / 2;
        assert defComp == expectedDef
            : "defective scanner: expected N*(N-1)/2=" + expectedDef
              + "; got " + defComp;
        assert fixComp == N - 1
            : "fixed scanner: expected N-1=" + (N - 1) + "; got " + fixComp;
        assert ratio > 50.0
            : "ratio should be >50x at N=300; got " + ratio;

        System.out.printf(
            "PASS testScannerRatioAtScale  (defective=%d, fixed=%d, ratio=%.0fx)%n",
            defComp, fixComp, ratio);
    }

    /**
     * Test 3 — nestjs-0002: getInjectionProviders defective is O(P*W*(R+S)), fixed is O(P*W).
     *
     * P=50 providers, W=10 iterations: ratio > 10x expected.
     */
    static void testGetInjectionProvidersRatio() {
        int P = 50;
        int W = 10;

        long defComp = getInjectionProvidersDefective(P, W);
        long fixComp = getInjectionProvidersFixed(P, W);
        double ratio = (double) defComp / fixComp;

        assert defComp > fixComp
            : "defective should have more comparisons than fixed; def="
              + defComp + " fix=" + fixComp;
        assert ratio > 3.0
            : "ratio should be >3x at P=50, W=10; got " + ratio;

        System.out.printf(
            "PASS testGetInjectionProvidersRatio  (defective=%d, fixed=%d, ratio=%.1fx)%n",
            defComp, fixComp, ratio);
    }

    /**
     * Test 4 — nestjs-0002 at larger scale: P=200 providers, W=15 iterations.
     * Ratio should be > 10x.
     */
    static void testGetInjectionProvidersRatioLargeScale() {
        int P = 200;
        int W = 15;

        long defComp = getInjectionProvidersDefective(P, W);
        long fixComp = getInjectionProvidersFixed(P, W);
        double ratio = (double) defComp / fixComp;

        assert ratio > 10.0
            : "ratio should be >10x at P=200, W=15; got " + ratio;

        System.out.printf(
            "PASS testGetInjectionProvidersRatioLargeScale  (defective=%d, fixed=%d, ratio=%.1fx)%n",
            defComp, fixComp, ratio);
    }

    // =========================================================================

    public static void main(String[] args) {
        testScannerCorrectnessMatch();
        testScannerRatioAtScale();
        testGetInjectionProvidersRatio();
        testGetInjectionProvidersRatioLargeScale();
        System.out.println("All NestJS tests passed.");
    }
}