java-topology/defects/jitsi-meet-0001/unit/JitsiMeetTransportDedupTest.java

package unit;

import java.util.*;

/**
 * Models jitsi-meet ConnectionStatsTable._renderTransport() dedup pattern.
 *
 * Defect: 5x array.includes() O(T) inside for-loop over T transport entries — O(T²).
 * Fix:    5x Set.has() O(1) for membership — O(T).
 *
 * jitsi-meet-0001 MOAD-0001 CWE-407
 * No JUnit — compile and run standalone.
 */
public class JitsiMeetTransportDedupTest {

    record Transport(String remoteIP, String localIP, String localPort,
                     String remotePort, String transportType) {}

    // -------------------------------------------------------------------
    // DEFECT: O(T²) — List.contains() inside loop, 5 checks per entry
    // -------------------------------------------------------------------
    static long slowDedup(List<Transport> transports) {
        List<String> remoteIP = new ArrayList<>();
        List<String> localIP  = new ArrayList<>();
        List<String> localPort = new ArrayList<>();
        List<String> remotePort = new ArrayList<>();
        List<String> transportType = new ArrayList<>();
        long ops = 0;
        for (Transport t : transports) {
            ops += remoteIP.size();
            if (!remoteIP.contains(t.remoteIP()))     remoteIP.add(t.remoteIP());
            ops += localIP.size();
            if (!localIP.contains(t.localIP()))       localIP.add(t.localIP());
            ops += localPort.size();
            if (!localPort.contains(t.localPort()))   localPort.add(t.localPort());
            ops += remotePort.size();
            if (!remotePort.contains(t.remotePort())) remotePort.add(t.remotePort());
            ops += transportType.size();
            if (!transportType.contains(t.transportType())) transportType.add(t.transportType());
        }
        return ops;
    }

    // -------------------------------------------------------------------
    // FIX: O(T) — Set.contains() O(1), arrays still built for output
    // -------------------------------------------------------------------
    static long fastDedup(List<Transport> transports) {
        List<String> remoteIP = new ArrayList<>();
        List<String> localIP  = new ArrayList<>();
        List<String> localPort = new ArrayList<>();
        List<String> remotePort = new ArrayList<>();
        List<String> transportType = new ArrayList<>();
        Set<String> seenRemoteIP = new HashSet<>();
        Set<String> seenLocalIP = new HashSet<>();
        Set<String> seenLocalPort = new HashSet<>();
        Set<String> seenRemotePort = new HashSet<>();
        Set<String> seenTransportType = new HashSet<>();
        long ops = 0;
        for (Transport t : transports) {
            ops++;
            if (seenRemoteIP.add(t.remoteIP()))         remoteIP.add(t.remoteIP());
            ops++;
            if (seenLocalIP.add(t.localIP()))           localIP.add(t.localIP());
            ops++;
            if (seenLocalPort.add(t.localPort()))       localPort.add(t.localPort());
            ops++;
            if (seenRemotePort.add(t.remotePort()))     remotePort.add(t.remotePort());
            ops++;
            if (seenTransportType.add(t.transportType())) transportType.add(t.transportType());
        }
        return ops;
    }

    static List<Transport> makeTransports(int n) {
        List<Transport> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new Transport(
                "10.0." + (i / 256) + "." + (i % 256),
                "192.168." + (i / 256) + "." + (i % 256),
                String.valueOf(5000 + i),
                String.valueOf(4000 + i),
                i % 2 == 0 ? "udp" : "tcp"
            ));
        }
        return list;
    }

    static List<Transport> makeDuplicateTransports(int n) {
        List<Transport> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // All entries share same fields — maximum dedup pressure
            list.add(new Transport("10.0.0.1", "192.168.1.1", "5000", "4000", "udp"));
        }
        return list;
    }

    public static void main(String[] args) {
        int tests = 0, passed = 0;

        // --- correctness: unique transports ---
        tests++;
        {
            List<Transport> inputs = makeTransports(10);
            // Both should produce same unique set sizes
            long slowOps = slowDedup(inputs);
            long fastOps = fastDedup(inputs);
            // Slow must have done more work than fast
            boolean ok = slowOps >= fastOps;
            System.out.printf("%s correctness-unique T=10 slowOps=%d fastOps=%d%n",
                ok ? "PASS" : "FAIL", slowOps, fastOps);
            if (ok) passed++;
        }

        // --- correctness: duplicate transports ---
        tests++;
        {
            List<Transport> inputs = makeDuplicateTransports(20);
            long slowOps = slowDedup(inputs);
            long fastOps = fastDedup(inputs);
            boolean ok = slowOps > fastOps;
            System.out.printf("%s correctness-dups T=20 slowOps=%d fastOps=%d%n",
                ok ? "PASS" : "FAIL", slowOps, fastOps);
            if (ok) passed++;
        }

        // --- speedup benchmarks ---
        int[] benchSizes = {20, 50, 100, 200};
        for (int n : benchSizes) {
            tests++;
            List<Transport> inputs = makeTransports(n);
            // Op counts as proxy for algorithmic complexity ratio
            long slowOps = slowDedup(inputs);
            long fastOps = fastDedup(inputs);
            double ratio = (double) slowOps / fastOps;
            // At T=50 unique entries: slow = 5 * sum(0..49) = 5*1225 = 6125; fast = 5*50 = 250 → 24.5x
            boolean ok = ratio >= 2.0;
            System.out.printf("%s speedup T=%d slowOps=%d fastOps=%d ratio=%.1fx%n",
                ok ? "PASS" : "FAIL", n, slowOps, fastOps, ratio);
            if (ok) passed++;
        }

        System.out.println("\n" + passed + "/" + tests + " PASS");
        if (passed != tests) System.exit(1);
    }
}