package unit;

import java.util.*;

/**
 * Unit test for actix-web-0001 and actix-web-0002: CWE-407 in actix-web.
 *
 * actix-web-0001 (MEDIUM):
 *   File:   actix-web/src/introspection.rs:984-989
 *   Symbol: update_unique — Vec::contains() inside a for loop
 *   Defect: Deduplication of route introspection data uses Vec::contains()
 *           which is O(N) per item. For M new items merged into an existing
 *           Vec of size N: O(N × M) total.
 *   Fix:    Build a HashSet from existing items; each insertion is O(1).
 *           Total: O(N + M).
 *
 * actix-web-0002 (MEDIUM):
 *   File:   actix-web-actors/src/ws.rs:431-435
 *   Symbol: handshake_with_protocols — protocols.iter().any() in .find()
 *   Defect: WebSocket protocol negotiation: for each client-requested protocol
 *           (R total), scan the server's supported list (P total): O(R × P)
 *           per upgrade request.
 *   Fix:    Pre-build HashSet<&str> from server protocols at handshake start.
 *           Each client protocol check is then O(1). Total: O(P + R).
 *
 * Modeled here in Java:
 *   Rust Vec::contains()       ≡  List<String> linear scan   (defective)
 *   Rust HashSet::contains()   ≡  HashSet<String> lookup     (fixed)
 *   Comparison counts tracked at the membership-test site.
 *
 * Expected at N=M=200 (actix-web-0001):
 *   defective comparisons ≈ N × M = 40,000
 *   fixed comparisons     ≈ N + M =    400
 *   ratio > 50×
 *
 * Expected at R=P=50 (actix-web-0002):
 *   defective comparisons = R × P = 2,500
 *   fixed comparisons     = R     =    50
 *   ratio = 50×
 */
public class ActixWebIntrospectionTest {

    // =========================================================================
    // actix-web-0001 model: update_unique with Vec vs HashSet
    // =========================================================================

    /**
     * Defective update_unique: uses List.contains() (O(N) scan) inside loop.
     * comparisons counts every element examined in contains().
     */
    static long updateUniqueDefective(List<String> existing, List<String> newItems,
                                      long[] comparisons) {
        for (String item : newItems) {
            // existing.contains(item) — O(existing.size()) linear scan
            boolean found = false;
            for (String x : existing) {
                comparisons[0]++;
                if (x.equals(item)) { found = true; break; }
            }
            if (!found) existing.add(item);
        }
        return comparisons[0];
    }

    /**
     * Fixed update_unique: builds a HashSet from existing, then inserts each
     * new item with O(1) HashSet.add (which returns false if already present).
     * comparisons counts one hash-probe per item.
     */
    static long updateUniqueFixed(List<String> existing, List<String> newItems,
                                   long[] comparisons) {
        Set<String> seen = new HashSet<>(existing);
        for (String item : newItems) {
            comparisons[0]++;   // O(1) HashSet.add
            if (seen.add(item)) {
                existing.add(item);
            }
        }
        return comparisons[0];
    }

    // =========================================================================
    // actix-web-0002 model: WebSocket protocol negotiation, slice vs HashSet
    // =========================================================================

    /**
     * Defective protocol negotiation: for each client protocol, scan server
     * protocols linearly (protocols.iter().any()).
     * Returns the first matched protocol, or null.
     * comparisons counts every element examined in the inner any() scan.
     */
    static String negotiateDefective(List<String> clientProtocols,
                                      List<String> serverProtocols,
                                      long[] comparisons) {
        for (String req : clientProtocols) {
            // protocols.iter().any(|p| p == req_p) — O(P) scan
            for (String srv : serverProtocols) {
                comparisons[0]++;
                if (srv.equals(req)) {
                    return req;  // first match wins
                }
            }
        }
        return null;
    }

    /**
     * Fixed protocol negotiation: pre-build HashSet from server protocols,
     * then check each client protocol with O(1) lookup.
     * comparisons counts one hash-probe per client protocol.
     */
    static String negotiateFixed(List<String> clientProtocols,
                                  List<String> serverProtocols,
                                  long[] comparisons) {
        // Build HashSet once: O(P)
        Set<String> serverSet = new HashSet<>(serverProtocols);
        for (String req : clientProtocols) {
            comparisons[0]++;   // O(1) HashSet.contains
            if (serverSet.contains(req)) {
                return req;
            }
        }
        return null;
    }

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

    /**
     * Test 1 — Correctness: defective and fixed update_unique produce same result.
     *
     * Existing: 50 unique strings. New: 50 strings (25 overlap + 25 novel).
     */
    static void testUpdateUniqueCorrectnessMatch() {
        List<String> existing1 = new ArrayList<>();
        List<String> existing2 = new ArrayList<>();
        List<String> newItems = new ArrayList<>();

        for (int i = 0; i < 50; i++) {
            existing1.add("item-" + i);
            existing2.add("item-" + i);
        }
        // 25 overlap (already in existing) + 25 novel
        for (int i = 25; i < 75; i++) newItems.add("item-" + i);

        long[] c1 = {0}, c2 = {0};
        updateUniqueDefective(existing1, newItems, c1);
        updateUniqueFixed(existing2, newItems, c2);

        assert new HashSet<>(existing1).equals(new HashSet<>(existing2))
            : "update_unique results differ";
        assert existing1.size() == 75
            : "expected 75 items (50 original + 25 novel); got " + existing1.size();

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

    /**
     * Test 2 — actix-web-0001: update_unique ratio at N=M=200.
     *
     * 200 existing items, 200 new unique items (no overlap — worst case for scan).
     * Defective: sum of scan sizes = 200 + 201 + ... + 399 ≈ O(N×M).
     * Fixed: 200 HashSet probes = O(M).
     * Ratio > 50×.
     */
    static void testUpdateUniqueRatioAtScale() {
        int N = 200, M = 200;

        List<String> existing1 = new ArrayList<>();
        List<String> existing2 = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            existing1.add("e" + i);
            existing2.add("e" + i);
        }
        // New items are all unique (no overlap) — worst case
        List<String> newItems = new ArrayList<>();
        for (int i = 0; i < M; i++) newItems.add("n" + i);

        long[] defComp = {0}, fixComp = {0};
        updateUniqueDefective(existing1, newItems, defComp);
        updateUniqueFixed(existing2, newItems, fixComp);

        assert new HashSet<>(existing1).equals(new HashSet<>(existing2))
            : "result mismatch";

        // Defective: scan sizes are N, N+1, ..., N+M-1 (each novel item extends list)
        long expectedDef = (long) N * M + (long) M * (M - 1) / 2;
        assert defComp[0] == expectedDef
            : "defective comparisons should be " + expectedDef + "; got " + defComp[0];

        // Fixed: M probes
        assert fixComp[0] == M
            : "fixed comparisons should be M=" + M + "; got " + fixComp[0];

        double ratio = (double) defComp[0] / fixComp[0];
        assert ratio > 50.0
            : "ratio should be >50× at N=M=200; got " + ratio;

        System.out.printf(
            "PASS testUpdateUniqueRatioAtScale  (N=%d M=%d defective=%d fixed=%d ratio=%.1fx)%n",
            N, M, defComp[0], fixComp[0], ratio);
    }

    /**
     * Test 3 — actix-web-0002 Correctness: both negotiators find same protocol.
     *
     * Client requests ["graphql-ws", "chat", "json-patch"].
     * Server supports ["json-patch", "graphql-ws"].
     * First match should be "graphql-ws" (first in client list that server knows).
     */
    static void testNegotiateCorrectnessMatch() {
        List<String> client = Arrays.asList("graphql-ws", "chat", "json-patch");
        List<String> server = Arrays.asList("json-patch", "graphql-ws");

        long[] c1 = {0}, c2 = {0};
        String defResult = negotiateDefective(client, server, c1);
        String fixResult = negotiateFixed(client, server, c2);

        assert "graphql-ws".equals(defResult)
            : "defective should find 'graphql-ws'; got " + defResult;
        assert defResult.equals(fixResult)
            : "negotiation result mismatch: defective=" + defResult + " fixed=" + fixResult;

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

    /**
     * Test 4 — actix-web-0002: protocol negotiation ratio at R=P=50, no match (worst case).
     *
     * No overlap between client and server protocols — full scan required.
     * Defective: R × P = 50 × 50 = 2,500 comparisons.
     * Fixed: R = 50 comparisons (one HashSet probe per client protocol).
     * Ratio = 50×.
     */
    static void testNegotiateRatioAtScale() {
        int R = 50, P = 50;

        List<String> client = new ArrayList<>();
        List<String> server = new ArrayList<>();
        // No overlap: client protocols start with "c-", server with "s-"
        for (int i = 0; i < R; i++) client.add("c-" + i);
        for (int i = 0; i < P; i++) server.add("s-" + i);

        long[] defComp = {0}, fixComp = {0};
        String defResult = negotiateDefective(client, server, defComp);
        String fixResult = negotiateFixed(client, server, fixComp);

        assert defResult == null : "defective should return null (no match); got " + defResult;
        assert fixResult == null : "fixed should return null (no match); got " + fixResult;

        long expectedDef = (long) R * P;
        assert defComp[0] == expectedDef
            : "defective comparisons should be R*P=" + expectedDef + "; got " + defComp[0];
        assert fixComp[0] == R
            : "fixed comparisons should be R=" + R + "; got " + fixComp[0];

        double ratio = (double) defComp[0] / fixComp[0];
        assert ratio == P
            : "ratio should be P=" + P + "; got " + ratio;

        System.out.printf(
            "PASS testNegotiateRatioAtScale  (R=%d P=%d defective=%d fixed=%d ratio=%.1fx)%n",
            R, P, defComp[0], fixComp[0], ratio);
    }

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

    public static void main(String[] args) {
        testUpdateUniqueCorrectnessMatch();
        testUpdateUniqueRatioAtScale();
        testNegotiateCorrectnessMatch();
        testNegotiateRatioAtScale();
        System.out.println("4/4 PASS");
    }
}