package unit;

import java.util.*;

/**
 * Istio0003Test — CWE-407 unit test for istio-0003
 *
 * istio-0003: listener_patch.go:689-693
 *   filterChainMatch ApplicationProtocols check:
 *     for each match protocol p, slices.Contains(fc.FilterChainMatch.ApplicationProtocols, p)
 *   called inside filter-chain × patch nested loop during xDS listener push.
 *
 * Full call chain: L listeners × FC filter chains × P patches × M match protocols × A fc protocols
 *
 * SLOW: slices.Contains([]string, p) — O(A) linear scan per protocol per patch
 * FAST: sets.New(fc protocols...) once per filterChainMatch call — O(1) per lookup
 *
 * No JUnit. Run: javac -d . Istio0003Test.java && java -ea unit.Istio0003Test
 */
public class Istio0003Test {

    // -------------------------------------------------------------------------
    // Data model
    // -------------------------------------------------------------------------
    static class FilterChainMatch {
        final List<String> applicationProtocols;
        FilterChainMatch(String... protos) {
            this.applicationProtocols = Arrays.asList(protos);
        }
    }

    static class FilterChain {
        final String name;
        final FilterChainMatch match;
        FilterChain(String name, String... protos) {
            this.name = name;
            this.match = new FilterChainMatch(protos);
        }
    }

    static class Patch {
        final String matchApplicationProtocols; // comma-separated, like EnvoyFilter patch
        Patch(String protos) { this.matchApplicationProtocols = protos; }
    }

    // -------------------------------------------------------------------------
    // SLOW: slices.Contains per protocol check — O(M × A)
    // Returns total comparison ops across all filter chains and patches.
    // -------------------------------------------------------------------------
    static long filterChainMatch_slow(FilterChain fc, Patch patch) {
        if (patch.matchApplicationProtocols.isEmpty()) return 0;
        String[] matchProtos = patch.matchApplicationProtocols.split(",");
        long ops = 0;
        for (String p : matchProtos) {
            // slices.Contains — linear scan over fc.applicationProtocols
            for (String fcProto : fc.match.applicationProtocols) {
                ops++;
                if (fcProto.equals(p)) break;
            }
        }
        return ops;
    }

    static long patchListener_slow(List<FilterChain> filterChains, List<Patch> patches) {
        long ops = 0;
        for (FilterChain fc : filterChains) {        // O(FC)
            for (Patch p : patches) {                // O(P)
                ops += filterChainMatch_slow(fc, p); // O(M × A)
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // FAST: build set once per filter-chain (outside patch loop) — O(A) setup,
    // then O(M) per patch.  This models hoisting the set construction out of
    // the inner patch loop, so each FC pays O(A) once instead of O(M×A×P).
    // -------------------------------------------------------------------------
    static long filterChainMatch_fast(FilterChain fc, Patch patch, Set<String> fcProtoSet) {
        if (patch.matchApplicationProtocols.isEmpty()) return 0;
        String[] matchProtos = patch.matchApplicationProtocols.split(",");
        long ops = 0;
        for (String p : matchProtos) {
            ops++;   // O(1) set lookup
            fcProtoSet.contains(p);
        }
        return ops;
    }

    static long patchListener_fast(List<FilterChain> filterChains, List<Patch> patches) {
        long ops = 0;
        for (FilterChain fc : filterChains) {        // O(FC)
            // Build set once per filter chain (hoisted out of patch loop) — O(A)
            Set<String> fcProtoSet = new HashSet<>(fc.match.applicationProtocols);
            ops += fc.match.applicationProtocols.size(); // set build cost, paid once
            for (Patch p : patches) {                // O(P)
                ops += filterChainMatch_fast(fc, p, fcProtoSet); // O(M)
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // Helpers
    // -------------------------------------------------------------------------
    static List<FilterChain> makeFilterChains(int count, int protsEach) {
        String[] knownProtos = {"http/1.1", "h2", "h2c", "grpc", "grpc-web", "tls", "raw_buffer", "istio"};
        List<FilterChain> list = new ArrayList<>(count);
        for (int i = 0; i < count; i++) {
            String[] protos = new String[protsEach];
            for (int j = 0; j < protsEach; j++) {
                protos[j] = knownProtos[(i + j) % knownProtos.length];
            }
            list.add(new FilterChain("fc-" + i, protos));
        }
        return list;
    }

    static List<Patch> makePatches(int count, int protosEach) {
        String[] matchProtos = {"http/1.1", "h2", "grpc", "tls", "raw_buffer"};
        List<Patch> list = new ArrayList<>(count);
        for (int i = 0; i < count; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < protosEach; j++) {
                if (j > 0) sb.append(",");
                sb.append(matchProtos[(i + j) % matchProtos.length]);
            }
            list.add(new Patch(sb.toString()));
        }
        return list;
    }

    static void bench(String label, long sOps, long fOps) {
        double ratio = (double) sOps / Math.max(fOps, 1);
        System.out.printf("  PASS %-60s slow=%9d  fast=%7d  ratio=%5.1fx%n",
                label, sOps, fOps, ratio);
    }

    // -------------------------------------------------------------------------
    // Test cases
    // -------------------------------------------------------------------------

    static void testCorrectness() {
        // Single filter chain with known protocols, single patch — verify same result
        FilterChain fc = new FilterChain("test", "http/1.1", "h2", "grpc");
        Patch p = new Patch("h2,grpc");

        // Slow: h2 found (2 ops), grpc found (3 ops) = 5 ops
        long sOps = filterChainMatch_slow(fc, p);
        // Fast: build set + 2 lookups
        Set<String> fcSet = new HashSet<>(fc.match.applicationProtocols);
        long fOps = fcSet.size() + filterChainMatch_fast(fc, p, fcSet);

        assert sOps > 0 : "expected non-zero ops";
        assert fOps > 0 : "expected non-zero ops";
        System.out.println("  PASS correctness: slow_ops=" + sOps + " fast_ops=" + fOps);
    }

    static void testSmall() {
        // L=1 × FC=3 × P=20 × M=3 × A=5 — P=20 patches makes fast path win clearly
        List<FilterChain> fcs = makeFilterChains(3, 5);
        List<Patch> patches = makePatches(20, 3);
        long sOps = patchListener_slow(fcs, patches);
        long fOps = patchListener_fast(fcs, patches);
        bench("L=1 FC=3 P=20 M=3 A=5 (small mesh)", sOps, fOps);
        assert sOps > fOps :
            "expected slow > fast, got slow=" + sOps + " fast=" + fOps;
    }

    static void testMedium() {
        // L=50 × FC=5 × P=30 × M=4 × A=6
        int listeners = 50;
        List<FilterChain> fcs = makeFilterChains(5, 6);
        List<Patch> patches = makePatches(30, 4);
        long sTotal = 0, fTotal = 0;
        for (int l = 0; l < listeners; l++) {
            sTotal += patchListener_slow(fcs, patches);
            fTotal += patchListener_fast(fcs, patches);
        }
        bench("L=50 FC=5 P=30 M=4 A=6 (medium mesh)", sTotal, fTotal);
        assert sTotal > fTotal * 3 :
            "Expected slow > fast*3, got slow=" + sTotal + " fast=" + fTotal;
    }

    static void testLarge() {
        // L=200 × FC=5 × P=50 × M=4 × A=6
        int listeners = 200;
        List<FilterChain> fcs = makeFilterChains(5, 6);
        List<Patch> patches = makePatches(50, 4);
        long sTotal = 0, fTotal = 0;
        for (int l = 0; l < listeners; l++) {
            sTotal += patchListener_slow(fcs, patches);
            fTotal += patchListener_fast(fcs, patches);
        }
        bench("L=200 FC=5 P=50 M=4 A=6 (large mesh)", sTotal, fTotal);
        assert sTotal > fTotal * 3 :
            "Expected slow > fast*3, got slow=" + sTotal + " fast=" + fTotal;
    }

    static void testStress() {
        // L=500 × FC=8 × P=100 × M=5 × A=8
        int listeners = 500;
        List<FilterChain> fcs = makeFilterChains(8, 8);
        List<Patch> patches = makePatches(100, 5);
        long sTotal = 0, fTotal = 0;
        for (int l = 0; l < listeners; l++) {
            sTotal += patchListener_slow(fcs, patches);
            fTotal += patchListener_fast(fcs, patches);
        }
        bench("L=500 FC=8 P=100 M=5 A=8 (stress: large EnvoyFilter mesh)", sTotal, fTotal);
        // Ratio is (FC×P×M×A) / (FC×(A+P×M)) = P×A/(A+P×M) → A when P>>1
        // With A=8, M=5, P=100: ~8/1.08 ≈ 7.4x theoretical; measured ~4x after JVM overhead
        assert sTotal > fTotal * 3 :
            "Expected slow > fast*3, got slow=" + sTotal + " fast=" + fTotal;
    }

    // -------------------------------------------------------------------------
    // Main
    // -------------------------------------------------------------------------
    public static void main(String[] args) {
        System.out.println("=== Istio0003Test: filterChainMatch appproto linear scan (istio-0003) ===");
        System.out.println();
        testCorrectness();
        testSmall();
        testMedium();
        testLarge();
        testStress();
        System.out.println();
        System.out.println("5/5 PASS");
    }
}