java-topology/defects/drone-0001/test/Drone0001Test.java

import java.util.*;

/**
 * Test for drone-0001: CWE-407 O(S*T) linear topic scan in InMemory pubsub Publish.
 *
 * Location: pubsub/inmem.go  InMemory.Publish() and inMemorySubscriber.Subscribe()
 *
 * Defect: for each subscriber (S), slices.Contains(sub.topics, topic) performs
 * an O(T) linear scan over topics. With S subscribers each holding T topics, one
 * Publish call costs O(S*T). Subscribe() and Unsubscribe() also use
 * slices.Contains inside their own loops.
 *
 * In a busy Drone CI instance running many concurrent SSE streams and
 * pipeline-event notifications this creates quadratic work per event published.
 *
 * Fix: maintain a map[string]struct{} topicSet alongside the topics slice.
 * hasTopic() becomes O(1) map lookup. Publish drops from O(S*T) to O(S).
 *
 * Speedup at S=500 subscribers, T=20 topics: 500*20=10000 ops vs 500 ops = 20x.
 *
 * Compile and run (no build tool required):
 *   javac defects/drone-0001/test/Drone0001Test.java -d /tmp/drone-0001
 *   java -cp /tmp/drone-0001 Drone0001Test
 */
public class Drone0001Test {

    private static int passed = 0;
    private static int failed = 0;

    // --- Defective subscriber: slice-based topic membership ---

    static class SubscriberDefective {
        final List<String> topics = new ArrayList<>();

        void addTopic(String t) {
            if (!topics.contains(t)) topics.add(t); // O(T) scan
        }

        boolean hasTopic(String t) {
            return topics.contains(t); // O(T) scan — defect site
        }
    }

    // --- Fixed subscriber: map-based topic membership ---

    static class SubscriberFixed {
        final Set<String> topicSet = new HashSet<>();

        void addTopic(String t) {
            topicSet.add(t); // O(1)
        }

        boolean hasTopic(String t) {
            return topicSet.contains(t); // O(1) — fix
        }
    }

    /**
     * Counts total element comparisons when Publish scans S subscribers,
     * each with T topics, and the publish topic is NOT present (worst case).
     */
    static long publishCostDefective(int S, int T, String publishTopic) {
        List<SubscriberDefective> subs = new ArrayList<>();
        for (int s = 0; s < S; s++) {
            SubscriberDefective sub = new SubscriberDefective();
            for (int t = 0; t < T; t++) sub.addTopic("t" + s + "." + t);
            subs.add(sub);
        }
        long ops = 0;
        for (SubscriberDefective sub : subs) {
            for (int i = 0; i < sub.topics.size(); i++) {
                ops++;
                if (sub.topics.get(i).equals(publishTopic)) break;
            }
        }
        return ops;
    }

    static long publishCostFixed(int S, int T, String publishTopic) {
        List<SubscriberFixed> subs = new ArrayList<>();
        for (int s = 0; s < S; s++) {
            SubscriberFixed sub = new SubscriberFixed();
            for (int t = 0; t < T; t++) sub.addTopic("t" + s + "." + t);
            subs.add(sub);
        }
        // one O(1) hash lookup per subscriber
        long ops = 0;
        for (SubscriberFixed sub : subs) {
            sub.hasTopic(publishTopic);
            ops++;
        }
        return ops;
    }

    // --- Tests ---

    static void testDefectiveQuadraticCost() {
        long cost100 = publishCostDefective(100, 20, "absent");
        long cost200 = publishCostDefective(200, 20, "absent");
        // doubling S doubles ops (O(S*T) with fixed T)
        check("defective cost at S=100,T=20 is exactly 2000",
            cost100 == 100L * 20);
        check("defective cost doubles when S doubles (O(S*T))",
            cost200 == cost100 * 2);
    }

    static void testFixedLinearCost() {
        long cost100 = publishCostFixed(100, 20, "absent");
        long cost200 = publishCostFixed(200, 20, "absent");
        check("fixed cost at S=100 is exactly 100 (one lookup per subscriber)",
            cost100 == 100);
        check("fixed cost at S=200 is exactly 200",
            cost200 == 200);
    }

    static void testSpeedupRatioAtScale() {
        int S = 500, T = 20;
        long defCost = publishCostDefective(S, T, "none");
        long fixCost = publishCostFixed(S, T, "none");
        double ratio = (double) defCost / fixCost;
        check("speedup at S=500,T=20 is at least 15x (expect ~20x)",
            ratio >= 15.0);
        System.out.printf("    drone-0001 publish cost: defective=%d fixed=%d ratio=%.1fx%n",
            defCost, fixCost, ratio);
    }

    static void testFixedSubscriberDeduplicates() {
        SubscriberFixed sub = new SubscriberFixed();
        sub.addTopic("events:pipeline");
        sub.addTopic("events:pipeline"); // duplicate
        sub.addTopic("events:repo");
        check("set-based subscriber deduplicates topics",
            sub.topicSet.size() == 2);
    }

    static void testFixedHasTopicCorrect() {
        SubscriberFixed sub = new SubscriberFixed();
        sub.addTopic("events:pipeline:exec");
        check("hasTopic returns true for subscribed topic",
            sub.hasTopic("events:pipeline:exec"));
        check("hasTopic returns false for unsubscribed topic",
            !sub.hasTopic("events:repo:push"));
    }

    static void testDefectiveHasTopicCorrect() {
        SubscriberDefective sub = new SubscriberDefective();
        sub.addTopic("events:pipeline:exec");
        check("defective hasTopic returns true for subscribed topic",
            sub.hasTopic("events:pipeline:exec"));
        check("defective hasTopic returns false for unsubscribed topic",
            !sub.hasTopic("events:repo:push"));
    }

    // --- Harness ---

    static void check(String desc, boolean cond) {
        if (cond) {
            System.out.println("  PASS: " + desc);
            passed++;
        } else {
            System.out.println("  FAIL: " + desc);
            failed++;
        }
    }

    public static void main(String[] args) {
        System.out.println("=== Drone0001Test (CWE-407 pubsub Publish O(S*T) topic scan) ===\n");

        testDefectiveQuadraticCost();
        testFixedLinearCost();
        testSpeedupRatioAtScale();
        testFixedSubscriberDeduplicates();
        testFixedHasTopicCorrect();
        testDefectiveHasTopicCorrect();

        System.out.println("\n--- " + passed + " passed, " + failed + " failed ---");
        if (failed > 0) System.exit(1);
    }
}